In this tutorial, we will write a Program to implement the Quick Sort algorithm in Kotlin programming language.

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 Data Structures and Algorithms in Kotlin

1. Bubble Sort Algorithm in Kotlin
2. Heap Sort Algorithm in Kotlin
3. Insertion Sort Algorithm in Kotlin
4. Merge Sort Algorithm in Kotlin
5. Quick Sort Algorithm in Kotlin
6. Selection Sort Algorithm in Kotlin
7. Stack Data Structure Implementation in Kotlin
   
8. Queue Data Structure Implementation in Kotlin
   
9. Deque Implementation in Kotlin
   
10. Singly Linked List Implementation in Kotlin
    
11. Doubly Linked List Implementation in Kotlin
    
12. Circular Linked List Implementation in Kotlin