Gnome sort, originally proposed by Hamid Sarbazi-Azad in 2000 and called Stupid sort, and then later on described by Dick Grune and named "Gnome sort", is a sorting algorithm

Sorting algorithm

In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...

 which is similar to insertion sort

Insertion sort

Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort...

, except that moving an element to its proper place is accomplished by a series of swaps, as in bubble sort

Bubble sort

Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which...

. It is conceptually simple, requiring no nested loops. The running time is O

Big O notation

In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...

(n²), but tends towards O(n) if the list is initially almost sorted. In practice the algorithm can run as fast as Insertion sort

Insertion sort

Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort...

. The average runtime is .

The algorithm always finds the first place where two adjacent elements are in the wrong order, and swaps them. It takes advantage of the fact that performing a swap can introduce a new out-of-order adjacent pair only right before or after the two swapped elements. It does not assume that elements forward of the current position are sorted, so it only needs to check the position directly before the swapped elements.

Description

Here is pseudocode

Pseudocode

In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...

 for the gnome sort using a zero-based array:


procedure gnomeSort(a[])
pos := 1
while pos < length(a)
if (a[pos] >= a[pos-1])
pos := pos + 1
else
swap a[pos] and a[pos-1]
if (pos > 1)
pos := pos - 1
else
pos := pos + 1
end if
end if
end while
end procedure


Example

Given an unsorted array, a = [5, 3, 2, 4], the gnome sort would take the following
steps during the while loop. The "current position" is highlighted in bold:

Current array	Action to take
[5, 3, 2, 4]	a[pos] < a[pos-1], swap:
[3, 5, 2, 4]	a[pos] >= a[pos-1], increment pos:
[3, 5, 2, 4]	a[pos] < a[pos-1], swap and pos > 1, decrement pos:
[3, 2, 5, 4]	a[pos] < a[pos-1], swap and pos <= 1, increment pos:
[2, 3, 5, 4]	a[pos] >= a[pos-1], increment pos:
[2, 3, 5, 4]	a[pos] < a[pos-1], swap and pos > 1, decrement pos:
[2, 3, 4, 5]	a[pos] >= a[pos-1], increment pos:
[2, 3, 4, 5]	a[pos] >= a[pos-1], increment pos:
[2, 3, 4, 5]	pos length(a), finished.

Optimization
The gnome sort may be optimized by introducing a variable to store the position before
traversing back toward the beginning of the list. This would allow the "gnome" to teleport

Teleportation

Teleportation is the fictional or imagined process by which matter is instantaneously transferred from one place to another.Teleportation may also refer to:*Quantum teleportation, a method of transmitting quantum data...

back to his previous position after moving a flower pot. With this optimization, the gnome
sort would become a variant of the insertion sort

Insertion sort

Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort...

.

Here is pseudocode

Pseudocode

In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...

 for an optimized gnome sort using a zero-based array:

procedure optimizedGnomeSort(a[])
pos := 1
last := 0
while pos < length(a)
if (a[pos] >= a[pos-1])
if (last != 0)
pos := last
last := 0
end if
pos := pos + 1
else
swap a[pos] and a[pos-1]
if (pos > 1)
if (last 0)
last := pos
end if
pos := pos - 1
else
pos := pos + 1
end if
end if
end while
end procedure


External links

• Gnome sort