Selection sort (Python, arrays)

From LiteratePrograms

Other implementations: C | C++ | C# | Erlang | Haskell | Java | Python, arrays

This is an example of the selection sort sorting algorithm, using an array package to sort in-place.

Selection sort is a simple but inefficient sort — only to be used for short sequences and where an insertion sort would be too complex. At this point it is more folkloric than useful, best considered as a precursor to Heapsort.

theory

Selection sort, like insertion sort, works by maintaining the invariant that, given a division of the list into a prefix and suffix, the prefix is sorted while the suffix remains unsorted. Initially, the suffix is the entire sequence and the empty list is trivially sorted. At each step, we lengthen the prefix and shorten the suffix. Once the suffix is empty, the prefix is the entire sequence, sorted, and we are done.

Selection sort is a converse of insertion sort in that we form the sorted list by appending the minimum element from the unsorted remainder to the sorted prefix, instead of inserting an arbitrary element from the unsorted remainder into position in the sorted prefix.

practice

The algorithm is a straightforward transcription of the definition: for each suffix of the list, rotate its minimal element to the front.

Exercise: convert to an unstable sort by swapping instead of rotating

<<selection sort>>=
def ssort(seq):
    define rotate
    while len(seq):
        rotate(seq[:argmin(seq)+1])
        seq = seq[1:]

wrapping up

Unlike most array processing packages, Numeric Python doesn't offer an array rotation primitive. We perform the rotation by swapping the tail element with the remainder of the list, using the usual 3-step temporary variable idiom.

Question: why can't we use parallel assignment here?

<<define rotate>>=
def rotate(xs): tmp = xs[-1]; xs[1:] = xs[:-1]; xs[0] = tmp

and then package it up with a few short tests, of a random sequence and an already sorted sequence.

<<selection_sort.py>>=
from numpy import *
selection sort
if __name__ == "__main__":
        r, s = random.random(12), arange(12)
        ssort(r); ssort(s)
        print s
        print r
        print alltrue(argsort(r) == arange(len(r)))

These should produce output similar to the following:

[ 0  1  2  3  4  5  6  7  8  9 10 11]
[ 0.06376977  0.27476332  0.36759731  0.45234824  0.45865225  0.52016551
  0.58614923  0.61700966  0.77369209  0.7843824   0.82544842  0.95624826]
True

Download code