Sorting is one of the most common and essential operations in computer programming. It helps organize data in a specific order so that it can be searched, displayed, or processed more efficiently. Among all the sorting algorithms, Quick Sort stands out for its simplicity, speed, and clever use of the divide-and-conquer technique. It’s often the go-to algorithm when you need to sort large amounts of data quickly.
with hands-on learning.
get the skills and confidence to land your next move.
Quick Sort works by selecting a “pivot” element from the array, then dividing the array into two parts — elements smaller than the pivot and those larger than it. These parts are then sorted recursively until everything is in order. What makes Quick Sort powerful is that it performs sorting in place, meaning it doesn’t need extra memory like Merge Sort does. In this article, we’ll explore different Kotlin programs that implement Quick Sort in several ways, helping beginners understand both the logic and the code flow in a simple, step-by-step manner.
Program 1: Basic Quick Sort using Recursion
This is the most common and classic implementation of Quick Sort. It uses recursion to repeatedly divide the array based on the pivot and sort the smaller parts.
fun quickSort(arr: IntArray, low: Int, high: Int) {
if (low < high) {
val pivotIndex = partition(arr, low, high)
quickSort(arr, low, pivotIndex - 1)
quickSort(arr, pivotIndex + 1, high)
}
}
fun partition(arr: IntArray, low: Int, high: Int): Int {
val pivot = arr[high]
var i = low - 1
for (j in low until high) {
if (arr[j] <= pivot) {
i++
val temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
}
val temp = arr[i + 1]
arr[i + 1] = arr[high]
arr[high] = temp
return i + 1
}
fun main() {
val numbers = intArrayOf(10, 7, 8, 9, 1, 5)
println("Original Array: ${numbers.joinToString()}")
quickSort(numbers, 0, numbers.size - 1)
println("Sorted Array: ${numbers.joinToString()}")
}In this program, the partition function chooses the last element as the pivot and rearranges the array so that smaller elements appear before it. Then the quickSort function recursively sorts the left and right parts. It’s an easy and clear example for beginners to understand how recursion helps break a big sorting problem into smaller, manageable ones.
Program 2: Quick Sort Using the Middle Element as Pivot
In some cases, choosing the last element as the pivot might not be efficient, especially when the array is already nearly sorted. This version uses the middle element as the pivot for better performance in certain scenarios.
fun quickSortMidPivot(arr: IntArray, low: Int, high: Int) {
if (low < high) {
val pivotIndex = partitionMid(arr, low, high)
quickSortMidPivot(arr, low, pivotIndex - 1)
quickSortMidPivot(arr, pivotIndex + 1, high)
}
}
fun partitionMid(arr: IntArray, low: Int, high: Int): Int {
val mid = (low + high) / 2
val pivot = arr[mid]
var left = low
var right = high
while (left <= right) {
while (arr[left] < pivot) left++
while (arr[right] > pivot) right--
if (left <= right) {
val temp = arr[left]
arr[left] = arr[right]
arr[right] = temp
left++
right--
}
}
return left
}
fun main() {
val numbers = intArrayOf(29, 10, 14, 37, 13)
println("Original Array: ${numbers.joinToString()}")
quickSortMidPivot(numbers, 0, numbers.size - 1)
println("Sorted Array: ${numbers.joinToString()}")
}This approach divides the array based on a pivot chosen from the middle instead of the end. It helps reduce the risk of poor performance when dealing with sorted or nearly sorted data. For beginners, this method is a great way to see how changing the pivot selection can influence the efficiency of Quick Sort.
Program 3: Quick Sort in Descending Order
While most sorting examples focus on ascending order, sometimes you need the opposite — to arrange numbers from largest to smallest. This version shows how a simple change can achieve that.
fun quickSortDescending(arr: IntArray, low: Int, high: Int) {
if (low < high) {
val pivotIndex = partitionDescending(arr, low, high)
quickSortDescending(arr, low, pivotIndex - 1)
quickSortDescending(arr, pivotIndex + 1, high)
}
}
fun partitionDescending(arr: IntArray, low: Int, high: Int): Int {
val pivot = arr[high]
var i = low - 1
for (j in low until high) {
if (arr[j] >= pivot) {
i++
val temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
}
val temp = arr[i + 1]
arr[i + 1] = arr[high]
arr[high] = temp
return i + 1
}
fun main() {
val numbers = intArrayOf(5, 8, 1, 3, 7, 9, 2)
println("Original Array: ${numbers.joinToString()}")
quickSortDescending(numbers, 0, numbers.size - 1)
println("Sorted in Descending Order: ${numbers.joinToString()}")
}The main change here is in the comparison inside the partition function. Instead of checking if an element is smaller than the pivot, we check if it is greater. This simple tweak flips the sorting order, giving a powerful lesson on how algorithms can be easily adjusted for different needs.
Program 4: Quick Sort Using Kotlin Collections
Kotlin’s collection framework allows us to handle sorting elegantly with List and MutableList. This version uses a more functional approach that feels clean and readable.
fun quickSortList(list: List<Int>): List<Int> {
if (list.size < 2) return list
val pivot = list[list.size / 2]
val equal = list.filter { it == pivot }
val less = list.filter { it < pivot }
val greater = list.filter { it > pivot }
return quickSortList(less) + equal + quickSortList(greater)
}
fun main() {
val numbers = listOf(10, 80, 30, 90, 40, 50, 70)
println("Original List: $numbers")
val sortedList = quickSortList(numbers)
println("Sorted List: $sortedList")
}This functional-style approach doesn’t modify the list directly but creates new sublists for elements smaller, equal to, and greater than the pivot. It’s very readable and fits Kotlin’s style perfectly. Although it uses more memory, it’s a great way for beginners to see how sorting can be expressed in a clear and expressive way using Kotlin’s modern features.
Frequently Asked Questions (FAQ)
Here are some common questions learners ask about Quick Sort in Kotlin.
Q1: What is Quick Sort in Kotlin?
Quick Sort is a divide-and-conquer algorithm that selects a pivot element and divides the array into smaller parts around that pivot, sorting them recursively.
Q2: Why is Quick Sort called “Quick”?
It’s called Quick because it generally performs faster than other sorting algorithms like Bubble Sort or Insertion Sort, especially for large data sets.
Q3: Is Quick Sort faster than Merge Sort?
In many cases, yes. Quick Sort is usually faster in practice because it sorts in place and requires less additional memory.
Q4: Can Quick Sort handle duplicate elements?
Yes, Quick Sort works fine with duplicates, but handling them properly (like in the list-based version) ensures stable results.
Q5: Is Quick Sort a stable algorithm?
No, the standard version of Quick Sort is not stable, meaning equal elements might not retain their original order.
Conclusion
Quick Sort is a powerful and efficient sorting algorithm that every Kotlin programmer should understand. It combines speed with elegance, showing how breaking a problem into smaller pieces can lead to quick solutions. Whether you use recursion, a middle pivot, or Kotlin’s modern list functions, each version teaches you something valuable about algorithm design and problem-solving.
By practicing these examples, you’ll not only get comfortable with sorting techniques but also strengthen your understanding of recursion, arrays, and Kotlin’s functional style. Keep experimenting, change the pivot logic, or modify the sorting order — and soon you’ll master Quick Sort in Kotlin with full confidence.
