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