Table of content

## Gnome Sort in kotlin

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 are 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.

### Gnome Sort Algorithm

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 backward 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 first two values:
33 98 74 13 55 20 77 45 64 83

Given that they are in the correct order we leave these 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 98 74 13 55 20 77 45 64 83

We can see that these two are not in the correct order, so we swap them:
33 74 98 13 55 20 77 45 64 83

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 backward. We compare the current item to the preceding item in the data set:
33 74 98 13 55 20 77 45 64 83

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 98 13 55 20 77 45 64 83

They’re out of order, so we swap them:
33 74 13 98 55 20 77 45 64 83

… and we keep bubbling backward until we reach either a value that is smaller or the head of the list:
33 74 13 98 55 20 77 45 64 83
33 13 74 98 55 20 77 45 64 83
33 13 74 98 55 20 77 45 64 83
13 33 74 98 55 20 77 45 64 83

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 backward 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]``````

### The complexity of Gnome sort

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)`.