By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,519 Members | 1,831 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,519 IT Pros & Developers. It's quick & easy.

sorting a list and counting interchanges

P: n/a
I have to sort a list, but in addition to the sorting, I need to
compute a phase factor that is +1 if there is an even number of
interchanges in the sort, and -1 if there is an odd number of
interchanges.

I could write a bubble sort, count the number of interchanges, and
compute the factor, but I have a feeling that there some
decorate-sort-undecorate solution buried in this problem somewhere.
However, I can't see it. Can anyone else help me with this?

I was thinking of something along the lines of zipping the list with a
range() of the same length, sorting that, and then counting the number
of times the second list has an item smaller than its previous item. In
other words

a = [1,10,2,7]
b = zip(a,range(len(a)))
b.sort()
a_sorted = [i for i,j in b]
order = [j for i,j in b]
phase = 0
for i in range(len(order)-1):
if order[i] > order[i+1]: phase += 1
phase = 2*(phase%2)-1

However, I can't prove that this works, and there's *got* to be a more
elegant way.

Thanks in advance,
Rick

Jul 18 '05 #1
Share this Question
Share on Google+
8 Replies


P: n/a
[RickMuller]
I have to sort a list, but in addition to the sorting, I need to
compute a phase factor that is +1 if there is an even number of
interchanges in the sort, and -1 if there is an odd number of
interchanges.


This sounds like a homework problem but will offer a solution anyway:
phase = 1
def mycmp(x, y): global phase
phase = -phase
return cmp(x, y)
sorted('abracadabra', cmp=mycmp) ['a', 'a', 'a', 'a', 'a', 'b', 'b', 'c', 'd', 'r', 'r'] phase

-1

Raymond Hettinger
Jul 18 '05 #2

P: n/a
[RickMuller]
I have to sort a list, but in addition to the sorting, I need to
compute a phase factor that is +1 if there is an even number of
interchanges in the sort, and -1 if there is an odd number of
interchanges.


It occurs to me that the previously posted comparison count won't do it.

The only idea that comes to mind is to do a selection sort and count the number
of swaps.

a = [1,10,2,7]
parity = 1
for i in xrange(len(a)-1):
x = a[i]
lowest = i
for j in xrange(i, len(a)):
if a[j] < a[lowest]:
lowest = j
if i != lowest:
a[i], a[lowest] = a[lowest], a[i]
parity = -parity
print 'swapping %d with %d. parity is %d' % (i, lowest, parity)
print parity, a
Raymond
Jul 18 '05 #3

P: n/a
Unless I'm mistaken, this doesnt quite work, because it switches the
parity of phase every time a comparison is made, rather than every time
a swap is made. So:

# <untested>
phase = 1
def mycmp(x,y):
global phase
c = cmp(x,y)
if c > 0: # i.e. a swap will be performed in the sort
phase = -phase
return c

Jul 18 '05 #4

P: n/a
[Jordan Rastrick]
Unless I'm mistaken, this doesnt quite work, because it switches the
parity of phase every time a comparison is made, rather than every time
a swap is made. So:

# <untested>
phase = 1
def mycmp(x,y):
global phase
c = cmp(x,y)
if c > 0: # i.e. a swap will be performed in the sort
phase = -phase
return c


You're right. An important test was omitted.
Raymond
Jul 18 '05 #5

P: n/a
On 6 Apr 2005 15:30:41 -0700, "RickMuller" <rp******@gmail.com> wrote:
I have to sort a list, but in addition to the sorting, I need to
compute a phase factor that is +1 if there is an even number of
interchanges in the sort, and -1 if there is an odd number of
interchanges.

I could write a bubble sort, count the number of interchanges, and
compute the factor, but I have a feeling that there some
decorate-sort-undecorate solution buried in this problem somewhere.
However, I can't see it. Can anyone else help me with this?


1. What is an "interchange"?

2. Without a definition that refers only to to the input and output,
one would have to say that "interchange" implies "event" and so the
number of interchanges would depend on the sorting method.

3. Of what practical use (or even esoteric academic interest) is the
parity of the number of interchanges?

Jul 18 '05 #6

P: n/a
On 6 Apr 2005 17:59:04 -0700, "Jordan Rastrick"
<jr*******@student.usyd.edu.au> wrote:
Unless I'm mistaken, this doesnt quite work, because it switches the
parity of phase every time a comparison is made, rather than every time
a swap is made. So:

# <untested>
phase = 1
def mycmp(x,y):
global phase
c = cmp(x,y)
if c > 0: # i.e. a swap will be performed in the sort
That's rather a wild assumption. It's not part of the language
definition that the first argument is at a lower index in the list
than the second argument. Perhaps it's been coded as though: c =
cmp(y, x); if c < 0: swap()

In any case I doubt if the OP's Data Structures & Algorithms 101 tutor
is interested in anything so practical as the implementation of
Python's list.sort() method :-)

phase = -phase
return c


Jul 18 '05 #7

P: n/a
John Machin <sj******@lexicon.net> writes:
1. What is an "interchange"?
Swapping two elements during the sort.
2. Without a definition that refers only to to the input and output,
one would have to say that "interchange" implies "event" and so the
number of interchanges would depend on the sorting method.
The number of interchanges depends on the sorting method, but whether
the number is odd or even is invariant. Every permutation of elements
is either an odd permutation or an even permutation.
3. Of what practical use (or even esoteric academic interest) is the
parity of the number of interchanges?


It is of considerable interest in combinatorics. The group of even
permutations on N elements is called the alternating group A(N).
It's an order-2 subgroup of the symmetric group S(N) which is the
group of all the permutations on N elements. The odd permutations
are of course a coset of A(N).
Jul 18 '05 #8

P: n/a
"Jordan Rastrick" <jr*******@student.usyd.edu.au> writes:
def mycmp(x,y):
global phase
c = cmp(x,y)
if c > 0: # i.e. a swap will be performed in the sort
phase = -phase
return c


That doesn't necessarily work. You don't know that c>0 will always
result in a swap. You don't know that the sorting algorithm necessarily
never swaps an element with itself. You have to find all the cycles in
the permutation and count the length of each one. Is this a homework
problem? If yes, the above should be enough of a hint.

Jul 18 '05 #9

This discussion thread is closed

Replies have been disabled for this discussion.