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

Shell Sort

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

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 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 backwards. We compare the current item to the preceeding 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 backwards 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 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]		

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

Bubble Sort

 
Join My Facebook Group
Join Group
 
aaaaaaaaaaaaa
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions

Recent Addition

new tutorial Selenium Online Training : Our next online training course for Selenium with Java starts from 17th December 2018.

You can attend first 3 classes for free, the total course fee is INR 10,000

The course time would be 8.00 PM(IST) for the first three classes

If you are interested to learn, then you can join the course by sending email to chercher.tech@gmail.com

or Register below


 
Join My Facebook Group
Join Group