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

About Author

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

Share this Article Facebook
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions