import java.util.Random;

/*

Gnome Sort is based on the technique used by the standard Dutch Garden Gnome (Du.: tuinkabouter).

Here is how a 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 backward.

Boundary conditions: if there is no previous pot, he steps forwards; if there is no pot next to him, he is done.

— "Gnome Sort - The Simplest Sort Algorithm". Dickgrune.com

*/

public class GnomeSort {

public static void main(String args[])

{

System.out.println("Sorting of randomly generated numbers using GNOME SORT");

Random random = new Random();

int N = 20;

int[] sequence = new int[N];

for (int i = 0; i < N; i++)

sequence[i] = Math.abs(random.nextInt(100));

System.out.println("\nOriginal Sequence: ");

printSequence(sequence);

System.out.println("\nSorted Sequence: ");

printSequence(gnomeSort(sequence));

}

static void printSequence(int[] sortedSequence)

{

for (int i = 0; i < sortedSequence.length; i++)

System.out.print(sortedSequence[i] + " ");

}

public static int[] gnomeSort(int arr[]){

int first = 1;

while(first < arr.length)

{

if (arr[first-1] <= arr[first])

{

first++;

}

else

{

int tmp = arr[first-1];

arr[first - 1] = arr[first];

arr[first] = tmp;

if (-- first == 0)

{

first = 1;

}

}

}

return arr;

}

}