1. Introduction
Sorting is a fundamental operation in computer science, and several algorithms are available for sorting data. One of the most popular algorithms used in sorting is quicksort. Quicksort is an efficient, recursive, and comparison-based sorting algorithm that uses a divide-and-conquer strategy.
In this tutorial, we’ll dive deep into the quicksort algorithm and explore its implementation in Kotlin. We’ll also include some variations with code implementations and unit test cases.
2. What Is the Quicksort Algorithm?
Quicksort is an efficient sorting algorithm that selects a pivot element from the array and partitions the other elements into two smaller slices or windows, according to whether they are less than or greater than the pivot element.
Subsequently, the two newly created slices are sorted recursively. The base cases of the recursion are array slices of size zero or one, which are already sorted.
It’s important to note that this sorting algorithm has a time complexity of O(n log n) on average and O(n^2) for the worst case. However, the worst-case scenario is rare, and the algorithm performs well in practice.
3. Implementation of Quicksort in Kotlin
Now that we have a basic idea about the quicksort algorithm let’s see how we can implement it in Kotlin.
First, we define a function quickSort() that takes an IntArray, left index, and right index as input parameters. We then define two variables start and end, representing the left and right boundaries, respectively, of the array slice we are currently sorting.
Additionally, we need to select a pivot element from the array, which is the middle element. We’ll use a while loop to partition the array into two slices, one with elements less than the pivot and the other with elements greater than the pivot. Lastly, we’ll sort both slices recursively:
fun quickSort(arr: IntArray, left: Int = 0, right: Int = arr.size - 1): IntArray {
var start = left
var end = right
val pivot = arr[(left + right) / 2]
while (start <= end) {
while (arr[start] < pivot) {
start++
}
while (arr[end] > pivot) {
end--
}
if (start <= end) {
val temp = arr[start]
arr[start] = arr[end]
arr[end] = temp
start++
end--
}
}
if (left < end) {
quickSort(arr, left, end)
}
if (start < right) {
quickSort(arr, start, right)
}
return arr
}
Now, let’s test our quicksort method:
@Test
fun `sorts an unsorted array`() {
val arr = intArrayOf(5, 3, 9, 7, 1)
val expected = intArrayOf(1, 3, 5, 7, 9)
assertArrayEquals(expected, quickSort(arr))
}
@Test
fun `sorts a sorted array`() {
val arr = intArrayOf(1, 2, 3, 4, 5)
val expected = intArrayOf(1, 2, 3, 4, 5)
assertArrayEquals(expected, quickSort(arr))
}
@Test
fun `sorts a reverse sorted array`() {
val arr = intArrayOf(5, 4, 3, 2, 1)
val expected = intArrayOf(1, 2, 3, 4, 5)
assertArrayEquals(expected, quickSort(arr))
}
It’s important to mention that the quicksort algorithm works on arrays of any Comparable objects as well, not just integers.
4. Various Partitioning Strategies
In addition to the partitioning strategy discussed in the previous section, there are other partitioning strategies that we can employ in the quicksort algorithm. The most popular ones are the Lomuto partition scheme and the Hoare partition scheme.
4.1. Lomuto’s Partitioning
The Lomuto partition scheme involves selecting the rightmost element of the Array as the pivot and partitioning the array into two slices such that all the elements to the left of the pivot are smaller than the pivot and all the elements to the right of the pivot are greater than or equal to the pivot. What’s more, the partitioning process involves iterating over the array and swapping elements that are smaller than the pivot with elements that are larger than the pivot.
Let’s implement the quicksort algorithm again using Lomuto’s Partitioning:
fun quickSortLomuto(arr: IntArray, start: Int = 0, end: Int = arr.size - 1) {
if (start < end) {
val pivot = partitionLomuto(arr, start, end)
quickSortLomuto(arr, start, pivot - 1)
quickSortLomuto(arr, pivot + 1, end)
}
}
fun partitionLomuto(arr: IntArray, start: Int, end: Int): Int {
val pivot = arr[end]
var i = start
for (j in start until end) {
if (arr[j] < pivot) {
val temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
i++
}
}
val temp = arr[i]
arr[i] = arr[end]
arr[end] = temp
return i
}
As usual, we need to test our method for correctness:
@Test
fun `sorts an unsorted array using lomuto's scheme`() {
val arr = intArrayOf(5, 3, 9, 7, 1)
quickSortLomuto(arr)
assert(arr.contentEquals(intArrayOf(1, 3, 5, 7, 9)))
}
@Test
fun `sorts a sorted array using lomuto's scheme`() {
val arr = intArrayOf(1, 2, 3, 4, 5)
quickSortLomuto(arr)
assert(arr.contentEquals(intArrayOf(1, 2, 3, 4, 5)))
}
@Test
fun `sorts a reverse sorted array using lomuto's scheme`() {
val arr = intArrayOf(5, 4, 3, 2, 1)
quickSortLomuto(arr)
assert(arr.contentEquals(intArrayOf(1, 2, 3, 4, 5)))
}
4.2. Hoare’s Partitioning
The Hoare partitioning scheme involves selecting two indices, one starting from the left and the other starting from the right, and moving them towards each other until they meet. This involves swapping elements that are on the wrong side of the pivot. The Hoare partition scheme is generally more efficient than Lomuto partition scheme, but it can be more complex to implement:
fun quickSortHoare(arr: IntArray, low: Int = 0, high: Int = arr.size - 1) {
if (low < high) {
val pivot = partitionHoare(arr, low, high)
quickSortHoare(arr, low, pivot)
quickSortHoare(arr, pivot + 1, high)
}
}
fun partitionHoare(arr: IntArray, low: Int, high: Int): Int {
val pivot = arr[low]
var start = low - 1
var end = high + 1
while (true) {
do {
start++
} while (arr[start] < pivot)
do {
end--
} while (arr[end] > pivot)
if (start >= end) {
return end
}
val temp = arr[start]
arr[start] = arr[end]
arr[end] = temp
}
}
Let’s go ahead and test this method, too:
@Test
fun `sorts an unsorted array using hoare's scheme`() {
val arr = intArrayOf(5, 3, 9, 7, 1)
quickSortHoare(arr)
assert(arr.contentEquals(intArrayOf(1, 3, 5, 7, 9)))
}
@Test
fun `sorts a sorted array using hoare's scheme`() {
val arr = intArrayOf(1, 2, 3, 4, 5)
quickSortHoare(arr)
assert(arr.contentEquals(intArrayOf(1, 2, 3, 4, 5)))
}
@Test
fun `sorts a reverse sorted array using hoare's scheme`() {
val arr = intArrayOf(5, 4, 3, 2, 1)
quickSortHoare(arr)
assert(arr.contentEquals(intArrayOf(1, 2, 3, 4, 5)))
}
5. Conclusion
In this article, we explored the quicksort algorithm and its implementation in Kotlin. We’ve seen how the algorithm works and how we can implement it with different partitioning schemes. In addition, we’ve written some unit test cases to verify the correctness of our implementation.
Quicksort is a powerful algorithm that is widely used in computer science, and understanding it is essential for any developer.
As always, the code samples and relevant test cases pertaining to this article can be found over on GitHub.