How to sort a list? NOT a newbie question.

[Alex Martelli]

"Tim Roberts" <timr at probo.com> wrote in message
news:4jcgqtsvc9dc7or96alisr6rhcv776qhd1 at 4ax.com...
    ...
> >This came up in the context of building the coefficients of polynomials
> >from a list of roots.  If complex roots occur in complex conjugate pairs,
> >then the resulting coefficients must be real, so I decided to cast the
> >coefficients to floats in this case.  A straightforward test is to take
> >the complex conjugate of each element of the list, then sort both lists
> >and see if they are the same.  As is clear from the above, that
definitely
> >didn't work!
>
> You can make this work if you can answer a couple of simple questions.
>
> Which is greater:  3 or 3j?
>
> Put these numbers in order:   3+0j  1+1j  1+2j  2+1j  2+2j   1+0j  0+3j

Any ordering will work for the original poster's application,
which is one of testing SETS -- he needs to test whether the
set of x's and the set of x.conjugate()'s are identical, as he
clearly explained in the just-quoted paragraph.

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!-)

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


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.


Alex