Quick Sort
Algorithms
#algorithms
#sorting
fun main() {
val arr = arrayOf(3, 1, 4, 4, 6, -1, 0)
quickSort(arr, 0, arr.size.dec())
println(arr.contentToString())
}
fun quickSort(arr: Array<Int>, low: Int, high: Int) {
if (low < high) {
val p = partition(arr, low, high)
quickSort(arr, low, p)
quickSort(arr, p.inc(), high)
}
}
fun partition(arr: Array<Int>, low: Int, high: Int): Int {
val mid = low.plus(high).div(2)
swap(arr, low, mid)
val pivot = arr[low]
var i = low
var j = high
while (true) {
while (arr[i] < pivot) i++
while (arr[j] > pivot) j--
if (i >= j) {
return j
}
swap(arr, i++, j--)
}
}
fun swap(arr: Array<Int>, i: Int, j: Int) {
val tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
}