is this sort method the same as the one in python 2.4

[Lowell Kirsh]

I'm trying to emulate the sorted() method introduced in python 2.4. The
only difference is that it takes a sequence as one of its arguments
rather than being a method of the sequence class. Does my method do the
same as the sorted()? The obvious difference is that my method is called
as sort(seq, cmp, key, reverse) rather than seq.sorted(cmp, key, reverse)

def sort(seq, cmp=None, key=None, reverse=False):
"return a sorted copy of its input"
if sys.version_info > (2,4):
return sorted(seq, cmp, key, reverse)
if key:
toreturn = [ (key(elt), elt) for elt in seq ]
else:
toreturn = seq[:]
if cmp:
toreturn.sort(cmp)
else:
toreturn.sort()
if key:
toreturn = [ b for (a,b) in toreturn ]
if reverse:
toreturn.reverse()
return toreturn


Lowell

 

[Raymond Hettinger]

"Lowell Kirsh"

I'm trying to emulate the sorted() method introduced in python 2.4. The
only difference is that it takes a sequence as one of its arguments
rather than being a method of the sequence class. Does my method do the
same as the sorted()?

Almost. This is closer to the mark:

def sorted(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


Try it against the tests in Lib/test/test_builtin.py.

The differences from your version:
* >= 2.4 rather than just > 2.4
* renamed the parameter to iterable
* handle the case where both cmp and key are defined
* add an enumerated tie breaker to prevent full key comparisons
* preserve by using reverse twice

The real sorted() does the same thing but is implemented a bit differently. A
custom key wrapper is applied to each object so that only the key value gets
compared (no need for a full tuple with a tie breaker value).

Raymond Hettinger

 

[Fredrik Lundh]

Almost. This is closer to the mark:

def sorted(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)

with your code

print sorted([1, 2, 3])

gives me a traceback that ends with

File "test.py", line 6, in sorted
return sorted(iterable, cmp, key, reverse)
File "test.py", line 6, in sorted
return sorted(iterable, cmp, key, reverse)
File "test.py", line 6, in sorted
return sorted(iterable, cmp, key, reverse)
File "test.py", line 5, in sorted
if sys.version_info >= (2,4):
RuntimeError: maximum recursion depth exceeded in cmp

the recursion isn't really that hard to explain, but the runtime error doesn't
really seem right...

:::

to fix the recursion, move the if-statement so you only define the function
if needed:

if sys.version_info < (2,4):
def sorted(...):
....

</F>

 

[Lowell Kirsh]

How come you reverse the list twice? And why does this preserve stability?

"Lowell Kirsh"

I'm trying to emulate the sorted() method introduced in python 2.4. The
only difference is that it takes a sequence as one of its arguments
rather than being a method of the sequence class. Does my method do the
same as the sorted()?

Almost. This is closer to the mark:

def sorted(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


Try it against the tests in Lib/test/test_builtin.py.

The differences from your version:
* >= 2.4 rather than just > 2.4
* renamed the parameter to iterable
* handle the case where both cmp and key are defined
* add an enumerated tie breaker to prevent full key comparisons
* preserve by using reverse twice

The real sorted() does the same thing but is implemented a bit differently. A
custom key wrapper is applied to each object so that only the key value gets
compared (no need for a full tuple with a tie breaker value).

Raymond Hettinger

 

[Pedro Werneck]

What about this ?


#
if sys.version_info >= (2,4):
def sorted(iterable, *args, **kwds):
seq = list(iterable)
seq.sort(*args, **kwds)
return seq
#

It worked against the TestSorted in lib/test/test_builtins.py

Almost. This is closer to the mark:

def sorted(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)

with your code

print sorted([1, 2, 3])

gives me a traceback that ends with

File "test.py", line 6, in sorted
return sorted(iterable, cmp, key, reverse)
File "test.py", line 6, in sorted
return sorted(iterable, cmp, key, reverse)
File "test.py", line 6, in sorted
return sorted(iterable, cmp, key, reverse)
File "test.py", line 5, in sorted
if sys.version_info >= (2,4):
RuntimeError: maximum recursion depth exceeded in cmp

the recursion isn't really that hard to explain, but the runtime error doesn't
really seem right...

:::

to fix the recursion, move the if-statement so you only define the function
if needed:

if sys.version_info < (2,4):
def sorted(...):
....

</F>

 

[Raymond Hettinger]

"Lowell Kirsh"

How come you reverse the list twice? And why does this preserve stability?

It's easy to see if you trace through the steps:

Given sample the following dataset and a desire to sort on the first field:

data = [('a', 1), ('a', 2), ('b', 3)]

Here are the step:

data.reverse()
data [('b', 3), ('a', 2), ('a', 1)]
data.sort(key=lambda record: record[0])
data [('a', 2), ('a', 1), ('b', 3)]
data.reverse()
data

[('b', 3), ('a', 1), ('a', 2)]

Note, in the final result, the two equal records (the ones with 'a') appear in
the same order as the original dataset (that is what stability means).

Now, try it without the initial reversal and note that stability is not
preserved:

data = [('a', 1), ('a', 2), ('b', 3)]
data.sort(key=lambda record: record[0])
data.reverse()
data

[('b', 3), ('a', 2), ('a', 1)]

Here's another way of accomplishing the original sort and preserving stability:

data = [('a', 1), ('a', 2), ('b', 3)]
sorted(data, cmp = lambda x,y: cmp(y[0], x[0]))

[('b', 3), ('a', 1), ('a', 2)]



Raymond Hettinger

 

[Raymond Hettinger]

"Pedro Werneck"

What about this ?


#
if sys.version_info >= (2,4):
def sorted(iterable, *args, **kwds):
seq = list(iterable)
seq.sort(*args, **kwds)
return seq
#

It worked against the TestSorted in lib/test/test_builtins.py

The key= and reverse= parameters were introduced to list.sort() in Py2.4.
Consequently, the above code won't provide the desired functionality in Py2.3
and prior.


Raymond Hettinger