🎓 Check Out My Top 25 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare

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

Bubble Sort Algorithm in Kotlin
Heap Sort Algorithm in Kotlin
Insertion Sort Algorithm in Kotlin
Merge Sort Algorithm in Kotlin
Quick Sort Algorithm in Kotlin
Selection Sort Algorithm in Kotlin
Stack Data Structure Implementation in Kotlin
Queue Data Structure Implementation in Kotlin
Deque Implementation in Kotlin
Singly Linked List Implementation in Kotlin
Doubly Linked List Implementation in Kotlin
Circular Linked List Implementation in Kotlin

My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:

Spring Boot + RabbitMQ Course - The Practical Guide

Java Guides

Search This Blog