Here is this module’s self-test code in action; the first tests sort dictionaries, and the
last sort tuples:
C:\...\PP4E\Dstruct\Classics> python sort1.py
[{'age': 32, 'name': 'doe'}, {'age': 25, 'name': 'john'}]
[{'age': 25, 'name': 'john'}, {'age': 32, 'name': 'doe'}]
[('doe', 32), ('john', 25)]
[('john', 25), ('doe', 32)]Adding comparison functions
Since functions can be passed in like any other object, we can easily allow for an optional
comparison function. In the next version, Example 18-26, the second argument takes
a function that should return true if its first argument should be placed before its
second. A lambda is used to provide an ascending-order test by default. This sorter also
returns a new sequence that is the same type as the sequence passed in, by applying the
slicing techniques used in the reversal tools earlier—if you sort a tuple of nodes, you
get back a tuple.
Example 18-26. PP4E\Dstruct\Classics\sort2.py
def sort(seq, func=(lambda x,y: x <= y)): # default: ascending
res = seq[:0] # return seq's type
for j in range(len(seq)):
i = 0
for y in res:
if func(seq[j], y): break
i += 1
res = res[:i] + seq[j:j+1] + res[i:] # seq can be immutable
return res
if name == 'main':
table = ({'name':'doe'}, {'name':'john'})
print(sort(list(table), (lambda x, y: x['name'] > y['name'])))
print(sort(tuple(table), (lambda x, y: x['name'] <= y['name'])))
print(sort('axbyzc'))
This time, the table entries are ordered per a field comparison function passed in:
C:\...\PP4E\Dstruct\Classics> python sort2.py
[{'name': 'john'}, {'name': 'doe'}]
({'name': 'doe'}, {'name': 'john'})
abcxyzThis version also dispenses with the notion of a field altogether and lets the passed-in
function handle indexing if needed. That makes this version much more general; for
instance, it’s also useful for sorting strings.
Data Structures Versus Built-ins: The Conclusion
But now that I’ve shown you these reversing and sorting algorithms, I need to also tell
you that they may not be an optimal approach, especially in these specific cases.
1400 | Chapter 18: Data Structures