Comb Sort in Kotlin | Data Structures

Comb Sort is an improvised version of bubble sort. The basic idea in comb sort is to eliminate the relatively smaller values situated to the end of the list. This is done as applying bubble sort on such an array would highly slow down the process.

In bubble sort, adjacent elements are compared and swapped if necessary to state them in a sorted order. The gap between elements being compared in bubble sort is 1. However, comb sort aims to improvise in this stage by allowing to compare elements with a gap much more than 1.

The internal program in bubble sort which swaps the elements is modified such that gap between the swapped elements goes down on each iteration of the outer loop with respect to a shrink factor 'k'. The value of k is generally set to 1.3 for better performance of comb sort.

Once the shrink factor is applied, the list is sorted with the new gap and further the process of reducing the gap is continued. The final stage obtained through this have most of their smaller elements towards the end of the list eliminated. Therefore, at this stage bubble sort can be implemented to reach the final sorted matrix.

Shell Sort Kotlin program for Comb sort


fun combSort(input: Array<Int>) {
    var gap = input.size
    if (gap <= 1) return  // already sorted
    var swaps = false
    while (gap > 1 || swaps) {
        gap = (gap / 1.247331).toInt()
        if (gap < 1) gap = 1
        var i = 0
        swaps = false
        while (i + gap < input.size) {
            if (input[i] > input[i + gap]) {
                val tmp = input[i]
                input[i] = input[i + gap]
                input[i + gap] = tmp
                swaps = true
            }
            i++
        }
    }
}

fun main(args: Array<String>) {
    val ia = arrayOf(28, 44, 46, 24, 25, 4, 1, 3)
    println("Unsorted : ${ia.contentToString()}")
    combSort(ia)
    println("Sorted   : ${ia.contentToString()}")
}


Output of the Patience sort in Kotlin


Unsorted : [28, 44, 46, 24, 25, 4, 1, 3]
Sorted   : [1, 3, 4, 24, 25, 28, 44, 46]		

Insertion Sort

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