Gnome sort is a sort 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 run slightly slower than bubble sort, although this depends on the details of the architecture and the implementation. In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... Insertion sort is a simple sort algorithm in which the sorted array (or list) is built one entry at a time. ... Bubble sort, also known as exchange sort, is a simple sorting algorithm. ... Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ... Bubble sort, also known as exchange sort, is a simple sorting algorithm. ...

Description

Here is pseudocode for the sort:

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

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.

Implementations

C#

 void GnomeSort( int[] array ) { for ( int i = 1, temp_value; i < array.Length; ) { if ( array[i-1] <= array[i] ) i += 1; else { temp_value = array[i-1]; array[i-1] = array[i]; array[i] = temp_value; i -= 1; if ( i == 0 ) i = 1; } } } 

The title given to this article is incorrect due to technical limitations. ...

C++

 #include <algorithm> // for std::swap void gnomeSort( int* array, int size ) { for ( int i = 1; i < size; ) { if ( array[i-1] <= array[i] ) { ++i; } else { std::swap( array[i-1], array[i] ); --i; if ( i == 0 ) { i = 1; } } } } 

C++ (pronounced see plus plus, IPA: ) is a general-purpose computer programming language. ...

Perl

 sub gnome_sort(@) { my @a = @_; my $i = 1; while ($i < @a) { if ($a[$i-1] <= $a[$i]) { $i++; } else { @a[$i-1, $i] = @a[$i, $i-1]; $i--; $i = 1 if $i == 0; } } return @a; } 

Programming Republic of Perl logo Perl, also Practical Extraction and Report Language (a backronym, see below), is a programming language released by Larry Wall on December 18, 1987 that borrows features from C, sed, awk, shell scripting (sh), and (to a lesser extent) from many other programming languages. ...

Python

 def gnome_sort(L): L = L[:] i = 1 while i < len(L): if L[i-1] <= L[i]: i += 1 else: L[i], L[i-1] = L[i-1], L[i] i -= 1 if i == 0: i = 1 return L 

Python is an interpreted programming language created by Guido van Rossum in 1990. ...

FORTRAN 77

 SUBROUTINE gnome_sort(A, LEN) INTEGER A, LEN, I, TEMP DIMENSION A(LEN) I = 2 WHILE (I .LE. LEN) DO IF ((I .EQ. 1) .OR. (A(I-1) .LE. A(I))) THEN I = I + 1 ELSE TEMP = A(I) A(I) = A(I-1) A(I-1) = TEMP I = I - 1 IF (I .EQ. 1) THEN I = 2 END IF END IF END WHILE END 

Fortran (also FORTRAN) is a statically typed, compiled, programming language originally developed in the 1950s and still heavily used for scientific computing and numerical computation half a century later. ...

Java

 public class GnomeSort { static void gnomeSort( int[] theArray ) { for ( int index = 1; index < theArray.length; ) { if ( theArray[index - 1] <= theArray[index] ) { ++index; } else { int tempVal = theArray[index]; theArray[index] = theArray[index - 1]; theArray[index - 1] = tempVal; --index; if ( index == 0 ) { index = 1; } } } } } 

The term Java can refer to: In geography: Java (island), the most populous island in Indonesia Javanese language, a language widely spoken on the island of Java Java coffee, a variety of coffee plant which originated on the island of Java, or a slang word for coffee Java Trench, a...

External link

• Gnome sort.