How to sort a list? NOT a newbie question.

[Michael James Barber]

In article <9o9ggs$sgs$1 at serv1.iunet.it>, Alex Martelli <aleax at aleax.it> wrote:
>
>Of course, thanks to Python's dictionaries, roughly O(1) for
>both insertion and membership-testing, there are better ways
>[O(n) ones] to perform this test than the O(n log n) approach
>of sorting lists.  Moreover, dictionaries are finely tuned
>so the multiplicative constants are also prety good -- not a
>big theoretical issue but definitely a practical one!-)
>
Definitely good points, and I'll probably be modifying my code to use this 
idea, if performance proves to be a problem.  

>E.g., the plainest and simplest approach would be OK:
>
>def all_coefficients_are_real(roots):
>    rootset={}
>    for root in roots:
>        rootset[root]=1
>    for root in roots:
>        if not rootset.has_key(root.conjugate()):
>            return 0
>    return 1
>
Actually, this won't work in general.  Consider having repeated roots of, 
say, [1j,1j,-1j].  

It needs to be slightly modified to something like:

def all_coefficient_are_real(roots):
  rootset = {}
  for root in roots:
    rootset[root] = rootset.get(root,0)+1
  for root in roots:
    if rootset[root] != rootset.get(root.conjugate(),0):
      return 0
  return 1

Untested, but it looks right.

>
>This doesn't mean that arbitrary-ordering sorts of complex
>numbers wouldn't be helpful in some other case -- just that,
>even if they were available, it might be best not to
>use them for this specific application.
>
I agree totally.  The list I asked about in the original post was really 
for rhetorical purposes:  one element of the list was another list, 
specifically to prevent this remapping to a dictionary.  I have to admit, 
I don't have any idea where I'd need to sort such a list--but of course, I 
probably would have said the same thing about lists with complex numbers 
about a week ago.

I'd like to thank all the respondents.  I've learned a bit, and definitely 
found the thread thought provoking so far.  Hopefully, others have as well.
-- 
					Michael J. Barber