Two Short Sorts
How short can a complete, competitive sort algorithm be? Less than half a dozen lines? Maybe just 3 or 4?
The question is not entirely academic. Occasionally, the need arises to do an ad-hoc sort of a few elements. In a lattice simulation, for instance, the need frequently arises to sort all the neighbors of a cell by some criterion: a short list, often containing not more than 4 element. In such cases, calling the built-in library routine is often inconvenient. This is particularly true for languages like Go that make sorting of arbitrary types difficult, but even in Python, which does not allow an arbitrary comparison operator in its sort routine, setting up the data structures for the library sort seems out of proportion. Wouldn’t it be great to do the sort inline?
Here are two of the shortest possible sort algorithms. Their average and worst-case time complexity is $n^2$, implying that they are not a good choice for larger data sets. But for truly small data sets, they are competitive, in particular once the setup overhead is taken into account.
One advantage that both of the following algorithms have is that the comparison is explicit and done only in a single place. This makes it easy to to supplement custom, possibly quite complex comparison criteria. (For example, sorting a list of objects by some deeply embedded fields, or comparing a second set of values if the objects are equal on the primary criterion.)
Exchange Sort
Exchange sort is a close relative to the random shuffle algorithm. The algorithm compares each element to all elements above it, swapping where necessary. It’s prime advantage is its extreme simplicity.
In Python:
data = [ 5, 3, 4, 2 ]
for i in range( len(data)-1 ):
for j in range( i+1, len(data) ):
if data[j] < data[i]:
data[i], data[j] = data[j], data[i]
In Go:
package main
func main() {
data := []int{ 4, 2, 3, 1 }
for i:=0; i<len(data)-1; i++ {
for j:=i+1; j<len(data); j++ {
if data[j] < data[i] {
data[j], data[i] = data[i], data[j]
}
}
}
}
Gnome Sort
Most standard sort algorithms either require a double loop (like insertion sort) or recursion (quicksort). Gnome sort makes do with a single loop (although it adjusts the loop index separately, resulting in an overall $n^2$ running time).
The algorithm was described by Hamid Sarbazi-Azad (who called it “Stupid Sort”) and Dick Grune. The latter named it “Gnome Sort”, because it reminded him of the way the “standard Dutch Garden Gnome” sorts a line of flower pots:
Basically, he looks at the flower pot next to him and the previous one; if they are in the right order he steps one pot forward, otherwise he swaps them and steps one pot backwards. Boundary conditions: if there is no previous pot, he steps forwards; if there is no pot next to him, he is done.
In Python:
data = [ 5, 3, 2, 4 ]
i = 0
while i < len(data):
if i==0 or data[i-1] <= data[i]:
i += 1
else:
data[i-1], data[i] = data[i], data[i-1]
i -= 1
In Go:
package main
func main() {
data := []int{ 5, 3, 2, 4 }
for i:=0; i<len(data); {
if i==0 || data[i-1] <= data[i] {
i += 1
} else {
data[i-1], data[i] = data[i], data[i-1]
i -= 1
}
}
}