Shell Sort in Kotlin

Shell sort in kotlin is the generalization of insertion sort which overcomes the drawbacks of insertion sort by comparing elements separated by a gap of several positions.

Shell sort allows sorting elements which are far apart. In case of insertion sort, comparison happens between only adjacent elements but in shell sort, it avoids comparing adjacent elements until the last step. The Last step of shell sort is ultimately insertion sort.

In short, it improves insertion sort by comparison and exchange elements that are far away.

Shell sort uses a sequence that can be referred as increment sequence. Shell sort makes multiple passes over the array and sort number of an equally sized array using insertion sort.

Bubble Sort in kotlin

Steps involved in Shell sort in Kotlin :

    • The basic principle of Shell sort is, Compare the first element with an element which a specific distance apart
    • We can calculate the distance based on various values like by dividing the array size by 2 (size/2), or any other value
    • Once we get the distance, then we start comparing the elements. For example,
      The first element with an element with distance away, and the second element with distance away from the second element, it goes on.
    • While comparing the first element with an element at a distance, we swap them only if the first element is larger than the element at the distance. Same applicable for all the elements
    • Once we are done with the first pass, hen we will go for seconds pass now we would be dividing the distance using the same logic that we used in first place
Only for the first time, we will be using the array size for division logic but after that, we will be using the distance we got from the previous pass.
  • In the end, we will have distance as 1, so this pass acts as insertion sort by comparing the adjacent elements

Cycle Sort in kotlin

Video Tutorial for Shell sort [Not mine but explains very well]

Subscribe to my youtube channel :


Shell Sort in Kotlin with Arrays

Code explanation for Shell Sort in kotlin

    • First, we got to decide on what based on what distance, we are going to perform the comparisons. I have chosen a gap/distance based on the array_size/2

      After the first iteration, we would be reducing the gap by dividing the previous gap by 2
var gap = n / 2
    • Iterate the till ten gap is more than zero
while (gap > 0)
    • Store the gap in a variable so that we can edit that variable from the next iteration. Also, make sure the maximum value that variable can have is the last index of the array
var i = gap
while (i < n) {
    • Now we have to compare the zeroth element with the element present at the gap, but from the next iteration, we should compare the element at index 1 with the element at gap+1

      Swap value between the comparison when the smaller index has bigger value than the value at a larger index.
val temp = arr[i]

// shift earlier gap-sorted elements up until the correct location for a[i] is found
var j = i
while (j >= gap && arr[j - gap] > temp) {
	arr[j] = arr[j - gap]
	j -= gap
}

// put temp (the original a[i]) in its correct
// location
arr[j] = temp
i += 1
    • Reduce the gap, that we have created earlier
gap /= 2

Pigeonhole Sort in kotlin


The complete code for shell sort in kotlin

/* function to sort array using shellSort in kotin*/
fun sort(arr: IntArray): Int {
    val n = arr.size

    // decide the gap, then reduce the gap
    var gap = n / 2
    while (gap > 0) {
        // Do a gapped insertion sort for this gap size.
        // The first gap elements a[0..gap-1] are already
		// in gapped order keep adding one more element
        // until the entire array is gap sorted
        var i = gap
        while (i < n) {
            // add a[i] to the elements that
			// have been gap sorted save a[i] in temp and make a hole at
            // position i
            val temp = arr[i]

            // shift earlier gap-sorted elements up until
			//the correct location for a[i] is found
            var j = i
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap]
                j -= gap
            }

            // put temp (the original a[i]) in its correct
            // location
            arr[j] = temp
            i += 1
        }
        gap /= 2
    }
    return 0
}
fun main(args: Array<String>) {
    val arr = intArrayOf(23, 12, 1, 8, 34, 54, 2, 3)
    println("Array before sorting")
    for( a in arr) print("$a  ")

    sort(arr)

    println("Array after sorting")
    for( a in arr) print("$a  ")
}

Bogo Sort in kotlin

Shell Sort in Kotlin with List

We can also create shell sort for lists in kotlin

fun MutableList<Int>.swap(index3: Int, index3: Int) {
    val tmp = this[index3]
    this[index3] = this[index3]
    this[index3] = tmp
}
fun MutableList<Int>.shellSort(): MutableList<Int> {
    var sublistCount = count() / 2
    while (sublistCount > 0) {
        var index = 0
        outer@while (index >= 0 && index < count()) {
            if (index + sublistCount >= count()) break
            if (this[index] > this[index + sublistCount]) {
                swap(index, index + sublistCount)
            }
            if (sublistCount == 1 && index > 0) {
                while (this[index - 1] > this[index] && index - 1 > 0) {
                    swap(index - 1, index)
                    index -= 1
                }
                index++
            } else {
                index++
                continue@outer
            }
        }
        sublistCount /= 2
    }
    return this
}
fun main(args: Array<String>) {
    var mutableListOfInt = mutableListOf(10, 4, 5, 2, 1, 3, 6, 9, 8, 7)
    print(mutableListOfInt.shellSort().toString())
}

Cocktail Sort in kotlin

Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions