Gnome sort

From Wikipedia, the free encyclopedia

Gnome sort is a sorting algorithm which is similar to insertion sort except that moving an element to its proper place is accomplished by a series of swaps, as in bubble sort. The name comes from the supposed behavior of the Dutch garden gnome in sorting a line of flowerpots. It is conceptually simple, requiring no nested loops. The running time is O(n²), and in practice the algorithm has been reported to generally run as fast as Insertion sort, although this depends on the details of the architecture and the implementation.

[edit] Description

Here is pseudocode for the sort:

 function gnomeSort(a[0..size-1]) {
  i := 1
  j := 2
  while i ≤ size
    if a[i-1] ≤ a[i]
        i := j
        j := j + 1 
    else
        swap a[i-1] and a[i]
        i := i - 1
        if i = 0
          i := 1
 }

Effectively, the algorithm always finds the first place where two adjacent elements are in the wrong order, and swaps them. If this place were searched for naively, the result would be O(n³). Instead, it takes advantage of the fact that performing a swap can only introduce a new out-of-order adjacent pair right before the two swapped elements, and so checks this position immediately after performing such a swap.