Home » Kotlin

Program for Quicksort in Kotlin

In this article, we are going to learn how to implement Quicksort in Kotlin? Here you will find what is merge sort, its algorithm, and program in Kotlin.
Submitted by Aman Gautam, on December 17, 2017

Quicksort is a sorting algorithm which uses Divide and Conquer approach like Merge Sort. Its worst-case running time is O(n2), but best an average running time is O(n log (n) ). It is an in-place sorting.

Here is the three-step divide-and-conquer process for sorting a typical subarray A[p ..r].

Divide: Partition the array A[p..r] into two subarrays A[p..q-1] and A[q+1..r] such that each element of A[p..q-1] is less than or equal to A[q], which is, in turn, less than or equal to each element of A[q+1..r]. Then Compute the index q as part of this partitioning procedure.

Conquer: Sort the two subarrays A[p..q-1] and A[q+1..r] by recursive calls to quicksort.

Combine: Because the subarrays are already sorted, no need to combine them, the entire array A[p ..r] is now sorted.

Algorithms

    QUICK_SORT(A,p,r)
    1.	if(p<r)
    2.	q=partition(A,p,r)
    3.	quick_sort(A,p,q-1)
    4.	quick_sort(A,q+1,r)

    PARTITION(A,p,r)
    1.	x= A[r]
    2.	I =p-1
    3.	for j=p to r-1
    4.	if A[j]<=x
    5.	i=i +i
    6.	exchange a[i] with a[j]
    7.	exchange a[i+1] with a[r]
    8.	return i+1

Algorithm source from Introduction to Algorithms by cormen

Program to implement Quicksort in Kotlin

fun quick_sort(A: Array<Int>, p: Int, r: Int) {
    if (p < r) {
        var q: Int = partition(A, p, r)
        quick_sort(A, p, q - 1)
        quick_sort(A, q + 1, r)

    }
}

fun partition(A: Array<Int>, p: Int, r: Int): Int {
    var x = A[r]
    var i = p - 1
    for (j in p until r) {
        if (A[j] <= x) {
            i++
            exchange(A, i, j)
        }
    }
    exchange(A, i + 1, r)
    return i + 1
}

fun exchange(A: Array<Int>, i: Int, j: Int) {
    var temp = A[i]
    A[i] = A[j]
    A[j] = temp
}

fun main(arg: Array<String>) {
    print("Enter no. of elements :")
    var n = readLine()!!.toInt()

    println("Enter elements : ")
    var A = Array(n, { 0 })
    for (i in 0 until n)
        A[i] = readLine()!!.toInt()

    quick_sort(A, 0, A.size - 1)

    println("Sorted array is : ")
    for (i in 0 until n)
        print("${A[i]}  ")
}

Output

Enter no. of elements :5
Enter elements :
10
34
22
56
74
Sorted array is :
10  22  34  56  74

Read more: Implementation of Quicksort in C++