The Gnome Sort is extremely simple, and is very similar to the principle behind the Insertion Sort .

The **Gnome Sort is yet another comparison and exchange sort** which has elements that are similar to the Bubble Sort. If you haven’t read up on the Bubble Sort, be sure to do that before reading this article as it may help with your understanding.

**Data set -**the array or list of items that is to be sorted.**n -**the number of elements in the data set.**Bubble -**perform a Bubble Sort-like shuffle of an item in a given direction.

The first principle to bear in mind when doing a Gnome Sort is that __as the algorithm progresses, all items to the left of the current item are always in order__. Each iteration of the algorithm moves the current item to the correct spot with respect to the previously sorted items.

The first part of the algorithm looks at the first two items in the data set and swaps them around if they are in the wrong order.

Then, for each iteration thereafter, the next item is bubbled backwards towards to head of the list until a value is encountered which is less than the current item (or the head of the list is reached). At this point, the current item is left alone, and the sort continues from the next item.

As per usual we will use the same initial data set that we used for the Bubble Sort and Cocktail Sort to aid in highlighting the differences.

The initial set looks like this:

33 98 74 13 55 20 77 45 64 83

The first step is to compare the firs two values:

Given that they are in the correct order we leave this two values alone. We can say that two items in the data set are **in order**.

Next we look at the item immediately after the **in order** items and compare that to the last sorted item:

33

We can see that these two are not in the correct order, so we swap them:

33

Given that we had to swap the values in the previous step, we can’t assume that the current item is in the right location with respect to the other **in order** items, and hence we need to continue to work backwards. We compare the current item to the preceeding item in the *data set*:

These two values are in the correct order, so we can now stop this iteration. At this point, the first three items in the set are sorted with respect to each other. Next, we move to the fourth item, and compare that with the last of the in order items:

33 74

They’re out of order, so we swap them:

33 74

… and we keep bubbling backwards until we reach either a value that is smaller or the head of the list:

33

33

Here we can see that 13 was the smallest number, so it was bubbled all the way to the head of the list. We then move on to the next iteration where we again compare the next item with the head of the list, and again __bubble backwards until we reach the correct location.__
Complete Gnome code example in Kotlin

```
fun gnomeSort(a: Array<Int>, ascending: Boolean = true) {
var i = 1
var j = 2
while (i < a.size)
if (ascending && (a[i - 1] <= a[i]) ||
!ascending && (a[i - 1] >= a[i]))
i = j++
else {
val temp = a[i - 1]
a[i - 1] = a[i]
a[i--] = temp
if (i == 0) i = j++
}
}
fun main(args: Array<String>) {
val array = arrayOf(100, 2, 56, 200, -52, 3, 99, 33, 177, -199)
println("Original : ${array.asList()}")
gnomeSort(array)
println("Sorted (asc) : ${array.asList()}")
gnomeSort(array, false)
println("Sorted (desc) : ${array.asList()}")
}
```

Output of the Gnome sort in Kotlin

```
Original : [100, 2, 56, 200, -52, 3, 99, 33, 177, -199]
Sorted (asc) : [-199, -52, 2, 3, 33, 56, 99, 100, 177, 200]
Sorted (desc) : [200, 177, 100, 99, 56, 33, 3, 2, -52, -199]
```

This is not a very efficient algorithm. It’s time and space complexity are exactly that of the Bubble Sort. That is, the time complexity is `O(n2)`

, and space complexity for in-place sorting is `O(1)`

.

| |||||

This article is written by Pavan, who is serving notice period in an MNC, Bangalore. He thought, let the articles speak rather than his image. He is also the same person who created the reporter for Protractor Jasmine