Quick Sort Algorithm in Kotlin

In this source code example, we will write a code to implement the Quick Sort algorithm in Kotlin.

Quicksort is a divide and conquer algorithm. To get the best performance, we would like to divide the sequence right down the middle into two equal-sized sequences. This would mean that we would have to pick the value exactly in the middle to be the pivot since the pivot is used to divide the two lists. 

For quicksort to have O(n log n) complexity, like merge sort, it must partition the list in O(n) time. We must choose a pivot quickly and we must choose it well. If we don’t choose a pivot close to the middle, we will not get the O(n log n) complexity we hope for. It turns out that choosing a random pivot from the list is good enough.

Quick Sort Algorithm in Kotlin

Let's write the Kotlin program to Sort an Array of elements in ascending order and descending order using the Quick Sort Algorithm:

import java.util.*

fun <E: Comparable<E>> Array<E>.sort() {
    sort(this, 0, size - 1)
}

private fun <E: Comparable<E>> sort(arr: Array<E>, low: Int, high: Int) {
    if (low < high) {
        val partitionIndex = partition(arr, low, high)

        sort(arr, low, partitionIndex - 1)
        sort(arr, partitionIndex + 1, high)
    }
}

private fun <E: Comparable<E>> partition(arr: Array<E>, low: Int, high: Int): Int {
    val pivot = arr[high]
    var i = low - 1
    for (j in low until high) {
        if (arr[j] <= pivot) {
            i++
            arr[i] = arr[j].also { arr[j] = arr[i] }
        }
    }
    arr[i + 1] = arr[high].also { arr[high] = arr[i + 1] }
    return i + 1;
}

fun <E: Comparable<E>> Array<E>.descending() {
    descending(this, 0, size - 1)
}

private fun <E: Comparable<E>> descending(arr: Array<E>, low: Int, high: Int) {
    if (low < high) {
        val partitionIndex = descendingPartition(arr, low, high)

        descending(arr, low, partitionIndex - 1)
        descending(arr, partitionIndex + 1, high)
    }
}

private fun <E: Comparable<E>> descendingPartition(arr: Array<E>, low: Int, high: Int): Int {
    val pivot = arr[high]
    var i = low - 1
    for (j in low until high) {
        if (arr[j] >= pivot) {
            i++
            arr[i] = arr[j].also { arr[j] = arr[i] }
        }
    }
    arr[i + 1] = arr[high].also { arr[high] = arr[i + 1] }
    return i + 1;
}

fun main(args: Array<String>) {
    println("Ascending Order")
    val nums = arrayOf(2, 12, 89, 23, 76, 43, 12)
    nums.sort()
    println(Arrays.toString(nums))

    val languages = arrayOf("Kotlin", "Java", "C", "C++", "R", "Python", "Matlab")
    languages.sort()
    println(Arrays.toString(languages))

    println()
    println("Descending Order")
    val numbers2 = arrayOf(2, 12, 89, 23, 76, 43, 12)
    numbers2.descending()
    println(Arrays.toString(numbers2))
    val list = arrayOf("Kotlin", "Java", "C", "C++", "R", "Python", "Matlab")
    list.descending()
    println(Arrays.toString(list))
}

Output:

Ascending Order
[2, 12, 12, 23, 43, 76, 89]
[C, C++, Java, Kotlin, Matlab, Python, R]

Descending Order
[89, 76, 43, 23, 12, 12, 2]
[R, Python, Matlab, Kotlin, Java, C++, C]

Related Algorithms in Kotlin


Comments