Sorting Networks

Bubble Sort and Quick sort

When sorting lists of some specific size, sorting networks are often employed. These are very simple devices that only do compare-exchange operations. A compare-exchange operation on the pair <x, y> is merely the following code.

if x > y then {t = x; x = y; y = t}

what did we learn from this?

Does did the direction matter?

5 Element Sorting network

What does this network do?

How to sort in Python

For example, here’s a case-insensitive string comparison:

>>>

>>> sorted("This is a test string from Andrew".split(), key=str.lower)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']

The value of the key parameter should be a function that takes a single argument and returns a key to use for sorting purposes. This technique is fast because the key function is called exactly once for each input record.

A common pattern is to sort complex objects using some of the object’s indices as keys. For example:

>>>

>>> student_tuples = [
    ('john', 'A', 15),
    ('jane', 'B', 12),
    ('dave', 'B', 10),
]
>>> sorted(student_tuples, key=lambda student: student[2])   # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]