Introsort in Kotlin

Introsort being a hybrid sorting algorithm uses three sorting algorithm to minimise the running time, Quicksort, Heapsort and Insertion Sort

Simply putting, it is the best sorting algorithm around. It is a hybrid sorting algorithm, which means that it uses more than one sorting algorithms as a routine.

Introsort begins with quicksort and if the recursion depth goes more than a particular limit it switches to Heapsort to avoid Quicksort’s worse case O(N2) time complexity.

It also uses insertion sort when the number of elements to sort is quite less. So first it creates a partition. Three cases arises from here.

  • If the partition size is such that there is a possibility to exceed the maximum depth limit then the Introsort switches to Heapsort. We define the maximum depth limit as 2*log(N)
  • If the partition size is too small then Quicksort decays to Insertion Sort. We define this cutoff as 16 (due to research). So if the partition size is less than 16 then we will do insertion sort.
  • If the partition size is under the limit and not too small (i.e- between 16 and 2*log(N)), then it performs a simple quicksort.

Since Quicksort can have a worse case O(N2) time complexity and it also increases the recursion stack space (O(log N) if tail recursion applied), so to avoid all these, we need to switch the algorithm from Quicksort to another if there is a chance of worse case. So Introsort solves this problem by switching to Heapsort.

Also due to larger constant factor, quicksort can perform even worse than O(N2) sorting algorithm when N is small enough. So it switches to insertion sort to decrease the running time of sorting.

Also if a bad pivot-selection is done then the quicksort does no better than the bubble-sort

Quicksort

Why is Insertion Sort used (and not Bubble Sort, etc)?

Insertion sort offers following advantages.

  • It is a known and established fact that insertion sort is the most optimal comparison-based sorting algorithm for small arrays.
  • It has a good locality of reference
  • It is an adaptive sorting algorithm, i.e- it outperforms all the other algorithms if the array elements are partially sorted.

Why is Heapsort used (and not Mergesort etc)?

This is solely because of memory requirements. Merge sort requires O(N) space whereas Heapsort is an in-place O(1) space algorithm.

Why is Heapsort not used in place of Quicksort when the partition size is under the limit ?

his question is same as why Quicksort generally outperforms Heapsort ? The answer is, although Heapsort also being O(N log N) in average as well as worse case and O(1) space also, we still don’t use it when the partition size is under the limit because the extra hidden constant factor in Heapsort is quite larger than that of Quicksort.

Insertion Sort Complete program for Introsort in kotlin


import java.*
import java.util.*

class IntroSort {
    
    private val size_threshold = 16
    fun sort(a: IntArray) {
        introsort_loop(a, 0, a.size, 2 * floor_lg(a.size))
    }

    fun sort(a: IntArray, begin: Int, end: Int) {
        if (begin < end) {
            introsort_loop(a, begin, end, 2 * floor_lg(end - begin))
        }
    }

    /* Quicksort algorithm modified for Introsort */
    private fun introsort_loop(a: IntArray, lo: Int, hi: Int, depth_limit: Int) {
        var hi = hi
        var depth_limit = depth_limit
        while (hi - lo > size_threshold) {
            if (depth_limit == 0) {
                heapsort(a, lo, hi)
                return
            }
            depth_limit = depth_limit - 1
            val p = partition(a, lo, hi, medianof3(a, lo, lo + (hi - lo) / 2 + 1, hi - 1))
            introsort_loop(a, p, hi, depth_limit)
            hi = p
        }
        insertionsort(a, lo, hi)
    }

    private fun partition(a: IntArray, lo: Int, hi: Int, x: Int): Int {
        var i = lo
        var j = hi
        while (true) {
            while (a[i] < x) i++
            j = j - 1
            while (x < a[j]) j = j - 1
            if (i >= j)
                return i
            exchange(a, i, j)
            i++
        }
    }

    private fun medianof3(a: IntArray, lo: Int, mid: Int, hi: Int): Int {
        return if (a[mid] < a[lo]) {
            if (a[hi] < a[mid])
                a[mid]
            else {
                if (a[hi] < a[lo])
                    a[hi]
                else
                    a[lo]
            }
        } else {
            if (a[hi] < a[mid]) {
                if (a[hi] < a[lo])
                    a[lo]
                else
                    a[hi]
            } else
                a[mid]
        }
    }

    /* Heapsort algorithm */
    private fun heapsort(a: IntArray, lo: Int, hi: Int) {
        val n = hi - lo
        run {
            var i = n / 2
            while (i >= 1) {
                downheap(a, i, n, lo)
                i = i - 1
            }
        }
        var i = n
        while (i > 1) {
            exchange(a, lo, lo + i - 1)
            downheap(a, 1, i - 1, lo)
            i = i - 1
        }
    }

    private fun downheap(a: IntArray, i: Int, n: Int, lo: Int) {
        var i = i
        val d = a[lo + i - 1]
        var child: Int
        while (i <= n / 2) {
            child = 2 * i
            if (child < n && a[lo + child - 1] < a[lo + child]) {
                child++
            }
            if (d >= a[lo + child - 1]) break
            a[lo + i - 1] = a[lo + child - 1]
            i = child
        }
        a[lo + i - 1] = d
    }

    /* Insertion sort algorithm */
    private fun insertionsort(a: IntArray, lo: Int, hi: Int) {
        var i: Int
        var j: Int
        var t: Int
        i = lo
        while (i < hi) {
            j = i
            t = a[i]
            while (j != lo && t < a[j - 1]) {
                a[j] = a[j - 1]
                j--
            }
            a[j] = t
            i++
        }
    }

    /* Common methods for all algorithms */
    private fun exchange(a: IntArray, i: Int, j: Int) {
        val t = a[i]
        a[i] = a[j]
        a[j] = t
    }

    private fun floor_lg(a: Int): Int {
        return Math.floor(Math.log(a.toDouble()) / Math.log(2.0)).toInt()
    }
}

fun main(args: Array<String>) {
    var intro  = IntroSort()
    var arr = intArrayOf(5,1,4,2,9,6)
    println(arr.contentToString())
    intro.sort(arr)
    println(arr.contentToString())
}


Output of the Introsort in kotlin


Before sorting : 
[5, 1, 4, 2, 9, 6]
After sorting : 
[1, 2, 4, 5, 6, 9]	

Pancake 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