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 to sort elements which are far apart. In case of insertion sort, comparison happens between only adjacent elements but in shell sort, it avoid comparing adjacent elements until last steps. 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 array and sort number of equally sized array using insertion sort.

Bubble Sort

Steps involved in Shell sort in Kotlin :

  • Basic principle of Shell sort is, Compare the first element with a 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 comapring the elements. For example,
    First element with an element with distance away, and second element with distance aways from second element, it goes so on.
  • While comparing the first element with a element at a distnce, 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 first pass, hen we will go for seconds pass now we would be dividing the distnce using the same logic that we used in first place
  • Only for the first time, we will be using the array size for devision logic but after that we will be using the distance we got from previous pass.
  • At end we will have distance as 1, so this pass acts as insertion sort by comparing the adjacent elements

Cycle Sort

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 comparisions. I have choosen a gap/distance based on the array_size/2

    After first iteration we would be reduing the gapby 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 tht variabel from next interation. Also make sure the maximum value that variable can have is 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 next iteration we should compare the element at index 1 with element at gap+1

    Swap value between the comparision when the smaller index has bigger value than value at 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


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

Shell Sort in Kotlin with List

We can also create shell sort for lists in koltin


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

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