[Tutor] Sort and compare

[Karl Pflästerer]

On 23 Oct 2003, Conrad Koziol <- arkamir at softhome.net wrote:

> def compare(a,b):
>          if a[1]>b[1]: return 0
>          else: return -1

This function has two bugs.  First it returns the wrong value for a[1]>
b[1]; it must return 1.  Second there are three cases: a > b, a == b, a
< b.

Python has a builtin `cmp' which you could use here.

        def mycmp(a, b):
              return cmp(a[1], b[1])
  
(the example is directly from the Python libraray reference).

> x = [('hello', 2), ('goodbye', 3), ('python', 1)]

> x.sort(compare(x))

> can you explain what happens to me step by step. That'a were im lost.

> Does x sort [-1, 0, 1, -1]????

Well with your function maybe (but where does the `1' come from?), but
if you used the right function: no.

Let's see (we best ask Python):

In [6]: def comp(a ,b):
   ...: m   print a, b, cmp( a[1], b[1])
   ...: m   return cmp(a[1], b[1])
   ...: m

In [7]: x = [('hello', 2), ('goodbye', 3), ('python', 1)]

In [8]: x.sort(comp)
('goodbye', 3) ('hello', 2) 1
('python', 1) ('goodbye', 3) -1
('python', 1) ('goodbye', 3) -1
('python', 1) ('hello', 2) -1

In [9]: x
Out[9]: [('python', 1), ('hello', 2), ('goodbye', 3)]


(I used IPython here; a great interactive environment).

So you see how the sort function compared the values till it found the
right ascending sequence.

For the sort function  a is greater than b if the comparing functions
returns -1; a is equal b if the function returns 0 and a is greater b if
the function returns +1.

*But* when you have bigger lists there are better possibilities than
using a custom compare function.  That's also written in the libraray
reference.  I quote a part of it here:
,----
|      A more time-efficient approach for reasonably-sized data
|      structures can often be used:
| 
|           tmplist = [(x[1], x) for x in mylist]
|           tmplist.sort()
|           mylist = [x for (key, x) in tmplist]
`----

You will need more space but most of the time that approach (decorate,
sort, undecorate) is faster.


   Karl
-- 
Please do *not* send copies of replies to me.
I read the list