Quicksort is a popular sorting algorithm that works by dividing an array into two smaller sub-arrays based on a chosen pivot element, such that all elements to the left of the pivot are smaller and all elements to the right are larger. The two sub-arrays are then recursively sorted using the same process, until the sub-arrays are so small that they are already sorted. The pivot element can be chosen in several ways, such as selecting the first, last, or middle element of the sub-array, or selecting a random element.
fun quicksort(arr: IntArray, left: Int, right: Int) {
if (left < right) {
val pivotIndex = partition(arr, left, right)
quicksort(arr, left, pivotIndex - 1)
quicksort(arr, pivotIndex + 1, right)
}
}The quicksort function takes an array of integers arr, the left index of the sub-array to sort (left), and the right index of the sub-array to sort (right). The function sorts the sub-array in place using the quicksort algorithm.
The quicksort function checks if the sub-array has more than one element (i.e., left < right). If the sub-array has only one element or is empty, the function does nothing. Otherwise, the function chooses a pivot element by calling the partition function and then recursively sorts the two sub-arrays to the left and right of the pivot element.
fun partition(arr: IntArray, left: Int, right: Int): Int {
val pivot = arr[right]
var i = left - 1
for (j in left until right) {
if (arr[j] <= pivot) {
i++
swap(arr, i, j)
}
}
swap(arr, i + 1, right)
return i + 1
}The partition function takes an array of integers arr, the left index of the sub-array to partition (left), and the right index of the sub-array to partition (right). The function chooses the pivot element to be the last element of the sub-array (arr[right]). The function then iterates through the sub-array from left to right, and swaps any element that is less than or equal to the pivot element with the element at the current position of the i index. After all elements have been processed, the pivot element is moved to its final position by swapping it with the element at arr[i + 1]. The function returns the index of the pivot element.
fun swap(arr: IntArray, i: Int, j: Int) {
val temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}The swap function is a helper function that swaps two elements of an array.
Quicksort has an average-case time complexity of O(n log n), where n is the number of elements in the array. This means that the time it takes to sort an array using quicksort increases logarithmically with the size of the array. However, in the worst case (e.g., when the array is already sorted or nearly sorted), quicksort has a time complexity of O(n^2). In practice, quicksort is often faster than other sorting algorithms, such as mergesort or heapsort, due to its cache efficiency and low overhead.
fun main() {
val arr = intArrayOf(20, 15, 81, 12, 6)
val index = quicksort(arr,0,arr.size-1)
for(i in 1 until arr.size)
println(arr[i])
}
fun quicksort(arr: IntArray, left: Int, right: Int) {
if (left < right) {
val pivotIndex = partition(arr, left, right)
quicksort(arr, left, pivotIndex - 1)
quicksort(arr, pivotIndex + 1, right)
}
}
fun partition(arr: IntArray, left: Int, right: Int): Int {
val pivot = arr[right]
var i = left - 1
for (j in left until right) {
if (arr[j] <= pivot) {
i++
swap(arr, i, j)
}
}
swap(arr, i + 1, right)
return i + 1
}
fun swap(arr: IntArray, i: Int, j: Int) {
val temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}