FOR FREE CONTENT

The Gnome sort is a comparison based sorting technique. It is also known as the stupid sort which is based on the sorting of flowerpots by Garden Gnome. The method of Gnome Sorting is:

Gnome looks at the flower pot next to him and the previous pot. If the pots are already incorrect order he steps one pot forward and if the pots are not in the correct order then he swaps the pot to get the correct order and steps back to the previous pot.

For the first pot, he is at the beginning of the sorting so he moves one-pot forward. When he reaches the last pot he is at the end of the sorting, he stops.

It is an in-place sorting algorithm as it does not require any extra space for sorting.

PROCEDURE WITH EXAMPLE:

Suppose we have an array of 4 elements as follows:

The array should be sorted in ascending order.

First, the first element is 12, it is the starting of the array, and there will be no swapping. The next element is 9. Now if we look to the previous element the element is 12, so they are not in the correct order, so, it will be swapped.

After this swapping we have to check the previous elements, but as it is already at the first position so the sorting will go forward and go to the next iteration.

In the next iteration, 12 and 10 will be compared; as they are not in the proper order they will be swapped.

Again as per procedure we also previous elements, 9 and 10 will be compared, as they are already in sorted order so there will be no swapping and it will go one index forward.

So again 10 and 12 will be compared. But there will be no swapping so the index will be forwarded by 1 and it will go for the next iteration.

Now, 12 and -2 will be compared and as they are not incorrect order they will be swapped.

In a similar way, 10 and -2 will be compared next, as they are also not in the correct order so they will be swapped again and the new array will be:

Next, 9 and -2 will be compared and again will be swapped. The array will now be:

The array now is already sorted. But according to the logic again it will compare -2 with 9. As they are already in sorted order, they will not be swapped.

As per login, we will compare the remaining elements as the order but all are already sorted.

INPUT: An unsorted array [98,34,12,.........,n]

OUTPUT: A sorted array[12,34,...............,n]

PROCESS:

Step 1: [Take the inputs from the user]

Read n
For i=0 to n repeat
Read arr[i]

Step 2: [Sort the array elements]
Set index <- 0
		while index < n repeat 
			if index =0 then 
				Set index=index+1
			if arr[index] ≥ arr[index - 1] then 
				Set index=index+1 
			else 
Swap arr[index] and arr[index-1]
				Set index=index-1 
Step 3:[Display the sorted array]
For i=0 to n repeat
Print arr[i]

Step 4: Stop.