Problem with the sort() function

[clementine]

Hi,

I have an array of arrays in the form of
list = [[3,'fork',0.3,1],[2,'fork,0.1,2],[3,'exec',0.2,2]]

The in-built sort(),list.sort() sorts on the first element, if the first
elts are equal then it sorts on the second elt and so on...But i really
dont want to search on the second elt if the first elts are equal...the
1-D lists shud be left in the same position i.e. i want the sorted list to
be [[2,'fork',0.1,2],[3,'fork,0.3,1],[3,'exec',0.2,2]] and not
[[2,'fork',0.1,2],[3,'exec',0.2,2],[3,'fork,0.3,1]].

I tried the following code:

def mysort(x,y):
return x[0]-y[0]

list.sort(mysort)

This somehow seems to work for a small subset of my input...but not for my
real input which has more than 2000 sub-lists(and so obviously i cant trace
each pass..). Can someone tell me what i'm missing?

 

[Nick Coghlan]

Hi,

I have an array of arrays in the form of
list = [[3,'fork',0.3,1],[2,'fork,0.1,2],[3,'exec',0.2,2]]

The in-built sort(),list.sort() sorts on the first element, if the first
elts are equal then it sorts on the second elt and so on...But i really
dont want to search on the second elt if the first elts are equal...the
1-D lists shud be left in the same position i.e. i want the sorted list to
be [[2,'fork',0.1,2],[3,'fork,0.3,1],[3,'exec',0.2,2]] and not
[[2,'fork',0.1,2],[3,'exec',0.2,2],[3,'fork,0.3,1]].

Try this:

Py> from operator import itemgetter
Py> list = [[3,'fork',0.3,1],[2,'fork',0.1,2],[3,'exec',0.2,2]]
Py> list.sort(key=itemgetter(0))
Py> list
[[2, 'fork', 0.10000000000000001, 2], [3, 'fork', 0.29999999999999999, 1], [3, '
exec', 0.20000000000000001, 2]]

If the 'key' argument isn't accepted (i.e. you aren't using Python 2.4), you'll
need to do the decoration manually:

def mysort(iterable, cmp=None, key=None, reverse=False):
"return a sorted copy of its input"
if sys.version_info >= (2,4):
return sorted(iterable, cmp, key, reverse)
seq = list(iterable)
if reverse:
seq.reverse() # preserve stability
if key is not None:
seq = [(key(elem), i, elem) for i, elem in enumerate(seq)]
seq.sort(cmp)
if key is not None:
seq = [elem for (key, i, elem) in seq]
if reverse:
seq.reverse()
return seq

list = mysort([[3,'fork',0.3,1],[2,'fork',0.1,2],[3,'exec',0.2,2]],
key=lambda x: x[0])

(Taken from Raymond's code in:
http://mail.python.org/pipermail/python-list/2005-January/263275.html)

Cheers,
Nick.

 

[clementine]

Thanx Nick...I forgot to mention im using python 2.2 and along with a host
of other things it doesnt seem to have the enumarate built in function
...is it possible to replace it by something else? I dont think
simulating it will be feasible....

 

[Sion Arrowsmith]

Thanx Nick...I forgot to mention im using python 2.2 and along with a host
of other things it doesnt seem to have the enumarate built in function
...is it possible to replace it by something else? I dont think
simulating it will be feasible....

Here's one I prepared earlier:

if sys.version_info < (2,3):
def enumerate(l):
return zip(range(len(l)), l)

which will suck somewhat on large lists compared to being able to
do it with iterators.

 

[Fuzzyman]

Here's one I prepared earlier:

if sys.version_info < (2,3):
def enumerate(l):
return zip(range(len(l)), l)

which will suck somewhat on large lists compared to being able to
do it with iterators.

Iterators are available in python 2.2
class enumerate:
def __init__(self, inlist):
self.inlist = inlist
self.index = 0

def next(self):
if self.index >= len(self.inlist): raise StopIteration
thisone = self.inlist[self.index]
self.index += 1
return self.index-1, thisone

def __iter__(self):
return self

Regards,

Fuzzy
http://www.voidspace.org.uk/python/index.shtml

--
\S -- (e-mail address removed) -- http://www.chaos.org.uk/~sion/
___ | "Frankly I have no feelings towards penguins one way or the other"
\X/ | -- Arthur C. Clarke
her nu becomeþ se bera eadward ofdun hlæddre heafdes bæce bump

bump bump

 

[Scott David Daniels]

def mysort(iterable, cmp=None, key=None, reverse=False):
"return a sorted copy of its input"
if sys.version_info >= (2,4):
return sorted(iterable, cmp, key, reverse)
seq = list(iterable)
if reverse:
seq.reverse() # preserve stability
if key is not None:
seq = [(key(elem), i, elem) for i, elem in enumerate(seq)]
seq.sort(cmp)
if key is not None:
seq = [elem for (key, i, elem) in seq]
if reverse:
seq.reverse()
return seq

You'd be better off defining things once (and using the standard name)
rather than doing a test every time your function is called.
Something like:

import sys
...
if sys.version_info < (2, 3):
def enumerate(iterable): # iterators not yet invented
return zip(range(len(iterable)), iterable)

if sys.version_info < (2, 4):
def sorted(iterable, cmp=None, key=None, reverse=False):
"return a sorted copy of its input"
seq = list(iterable)
if reverse:
seq.reverse() # preserve stability
if key is not None:
seq = [(key(elem), i, elem) for i, elem
in enumerate(seq)]
seq.sort(cmp)
if key is not None:
seq = [elem for (key, i, elem) in seq]
if reverse:
seq.reverse()
return seq

If you like your names better, you can use:

if sys.version_info >= (2, 4):
mysort = sorted
else:
def mysort(iterable, cmp=None, key=None, reverse=False):
...

or even (if you can't be bothered to look up when features happened):

try:
test = enumerate
except NameError:
def enumerate(iterable):
...
try:
test = sorted
except NameError:
def sorted(iterable, cmp=None, key=None, reverse=False):
...


--Scott David Daniels
(e-mail address removed)

 

[Duncan Booth]

if sys.version_info < (2, 4):
def sorted(iterable, cmp=None, key=None, reverse=False):
"return a sorted copy of its input"
seq = list(iterable)
if reverse:
seq.reverse() # preserve stability
if key is not None:
seq = [(key(elem), i, elem) for i, elem
in enumerate(seq)]
seq.sort(cmp)
if key is not None:
seq = [elem for (key, i, elem) in seq]
if reverse:
seq.reverse()
return seq

I think you may have some unintended indentation on the 'seq.sort' line
otherwise this only sorts when a key is specified.

Also, you probably want:

if key is not None:
if reverse:
seq = [(key(elem), -i, elem) for i, elem
in enumerate(seq)]
else:
seq = [(key(elem), i, elem) for i, elem
in enumerate(seq)]

to handle the case where both key and reverse are given.

 

[Steven Bethard]

Iterators are available in python 2.2
class enumerate:
def __init__(self, inlist):
self.inlist = inlist
self.index = 0

def next(self):
if self.index >= len(self.inlist): raise StopIteration
thisone = self.inlist[self.index]
self.index += 1
return self.index-1, thisone

def __iter__(self):
return self

A simpler version that works with any iterable (not just sequences):

py> class enumerate(object):
.... def __init__(self, iterable):
.... self._next = iter(iterable).next
.... self._index = -1
.... def __iter__(self):
.... return self
.... def next(self):
.... self._index += 1
.... return self._index, self._next()
....
py> enumerate('abcde')
<__main__.enumerate object at 0x011627F0>
py> list(enumerate('abcde'))
[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd'), (4, 'e')]

STeVe

 

[Steven Bethard]

or even (if you can't be bothered to look up when features happened):

try:
test = enumerate
except NameError:
def enumerate(iterable):
...
try:
test = sorted
except NameError:
def sorted(iterable, cmp=None, key=None, reverse=False):
...

Ridiculously minor nit, but there's no reason to assign to test:

try:
enumerate
except NameError:
def enumerate(iterable):
...
try:
sorted
except NameError:
def sorted(iterable, cmp=None, key=None, reverse=False):
...

Just evaluating the expression 'enumerate' or 'sorted' should raise the
NameError if they don't exist.

STeVe

 

[John Machin]

Thanx Nick...I forgot to mention im using python 2.2 and along with a host
of other things it doesnt seem to have the enumarate built in function
...is it possible to replace it by something else? I dont think
simulating it will be feasible....

Faced with Nick's one line of code that uses 'enumerate', you have the
choice of building (and testing) an elaborate time machine to make a
SLOW 'enumerate' available for 2.2, or you can just patch Nick's
sorting gadget in a very straightforward manner:

modern as per Nick:
seq = [(key(elem), i, elem) for i, elem in enumerate(seq)]

ancient:
seq = [(key(seq), i, seq) for i in xrange(len(seq))]

 

[clementine]

Thanks everyone!! Nicks solution coupled with John's modifications
worked great for 2.2!! Yipeee...!!