Programming Python, 3rd Edition

Sorting Sequences

Another staple of many systems is sorting: ordering items in a collection according to some constraint. The script in Example 20-24 defines a simple sort routine in Python, which orders a list of objects on a field. Because Python indexing is generic, the field can be an index or a key—this function can sort lists of either sequences or mappings.

Example 20-24. PP3E\Dstruct\Classics\sort1.py

def sort(list, field):
    res = []                                     # always returns a list
    for x in list:
        i = 0
        for y in res:
            if x[field] <= y[field]: break       # list node goes here?
            i = i+1
        res[i:i] = [x]                           # insert in result slot
    return res

if _ _name_ _ == '_ _main_ _':
    table = [ {'name':'john', 'age':25}, {'name':'doe', 'age':32} ]
    print sort(table, 'name')
    print sort(table, 'age')
    table = [ ('john', 25), ('doe', 32) ]
    print sort(table, 0)
    print sort(table, 1)

Here is this module’s self-test code in action:

C:\...\PP3E\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 20-25), 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 ...