# The proper idiom for sorting objects in a list by an arbitrary property

maxm maxm at normik.dk
Tue Sep 11 16:43:35 CEST 2001

```> And well indeed you do -- the decorate-sort-undecorate idiom
> that you use is invariably best.

I found a paper by Guido, after writing the sort routine. It seems that he
came to practically the same solution.

I wrote a few solutions, and it seems that Guidos is slightly faster than my
original method.:

regards Max M

Well it doesn't seem as important as what's happening in New York and
Washington right now. So I think I will go home. :-(

----------------------------------------------------------------------------

def sort(objects, sortAttrib):
# makes a list of tuples ('value of sortatrib', 'index')
sortValues = [(getattr(objects[i], sortAttrib), i)
for i in range(len(objects))]
sortValues.sort(), # Sorts by first value in tuple
return [objects[sortTuple[1]] for sortTuple in sortValues]

def sort2(objects, sortAttrib):

global _sortBy
_sortBy = sortAttrib

def sortByParam(val1, val2):
global _sortAttrib
attrib1 = getattr(val1, _sortBy)
attrib2 = getattr(val2, _sortBy)
if  attrib1 < attrib2:
return -1
elif attrib1 > attrib2:
return 1
return 0

objects.sort(sortByParam)
return objects

def sort3(objects, sortAttrib):
nlist = map(lambda object, sortAttrib=sortAttrib:
(getattr(object, sortAttrib), object), objects)
nlist.sort()
return map(lambda (key, object): object, nlist)

class my:
def __init__(self, id, title):
self.id    = id
self.title = title

import time, random

for n in [100, 1000, 10000, 20000, 30000, 100000]: #

# Make shure they sort the same list
theList = [my(random.random(), 'xxx') for i in range(n)]

print n, 'objects in list'
start1 = time.time()
sort(theList[:], 'id')
end1 = time.time()
print 'test1: ', end1-start1

start2 = time.time()
sort2(theList[:], 'id')
end2 = time.time()
print 'test2: ', end2-start2

start3 = time.time()
sort3(theList[:], 'id')
end3 = time.time()
print 'test3: ', end3-start3

print ''

----------------------------------------------------------------------------

100 objects in list
test1:  0.00999999046326
test2:  0.0
test3:  0.0

1000 objects in list
test1:  0.0600000619888
test2:  0.0699999332428
test3:  0.0199999809265

10000 objects in list
test1:  1.09200000763
test2:  1.07099997997
test3:  0.480999946594

20000 objects in list
test1:  0.901000022888
test2:  2.28299999237
test3:  0.72100007534

30000 objects in list
test1:  1.44200003147
test2:  3.56499993801
test3:  1.38199996948

100000 objects in list
test1:  5.96799993515
test2:  13.6000000238
test3:  4.78700006008

```