sorting a list and counting interchanges

[John Machin]

On 6 Apr 2005 17:59:04 -0700, "Jordan Rastrick"
<jrastrick at 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