Start learning free

LESSON 262 OF 348 · DIVIDE AND CONQUER

Quick Sort in Kotlin: Random Pivot, In-Place Partition

Practice O(n log n) Read the full explanation

In this video lesson we will study how the Quick Sort algorithm works, we will analyze its time and space complexities and then we will implement it:

Problem - Quick Sort:

Given an array of integers nums, sort it in ascending order using Quick Sort

Example 1:

Input: nums = [3, 1, 3, 2, 5, 4]
Output: [1, 2, 3, 3, 4, 5]

Note:

Your algorithm should run in O(n log n) time and use O(log n) extra space.

STEP 1 OF 18
    Ctrl + Enter to check

    KOTLIN · DIVIDE AND CONQUER

    Quick Sort in Kotlin, explained

    Problem overview

    Sort an IntArray named nums in ascending order with Quick Sort. The function sort(nums) returns nothing: it rearranges the array in place. For [3, 1, 3, 2, 5, 4] the result is [1, 2, 3, 3, 4, 5].

    The lesson asks for O(n log n) time and O(log n) extra space. That is the typical behaviour of Quick Sort with a random pivot: the array is sorted inside itself, and the only extra memory is the recursion stack.

    Approach

    Quick Sort works by partitioning:

    1. Pick a pivot value.
    2. Rearrange the range so that every value less than or equal to the pivot comes before it and every larger value after it. Now the pivot sits at its final sorted position.
    3. Sort the part before the pivot and the part after it with the same method.

    Unlike Merge Sort, no merge is needed afterwards: once both sides are sorted, the whole range is sorted, because everything on the left is no larger than everything on the right.

    The choice of pivot decides the running time. If the pivot is always the smallest or largest value, one side is empty each time and the work becomes O(n²). Picking the pivot at random makes such bad splits very unlikely, even on input that is already sorted.

    Step by step

    1. Start the recursion. sort calls quickSort(nums, 0, nums.size - 1). Both bounds are inclusive.
    2. Declare quickSort with the array and the two bounds. The array is passed by reference, so the recursion changes the caller's array.
    3. Base case. If left >= right, the range has at most one element and is already sorted. Return.
    4. Partition. val pivot = partition(nums, left, right) rearranges the range and returns the pivot's final index.
    5. Recurse on both sides. Sort left..pivot - 1 and pivot + 1..right. The pivot is left out because it is already in place.
    6. Write partition. It picks randomIndex in left..right and swaps that element to the end, so the pivot is out of the way while the loop runs. (left..right).random() picks from a closed range, so both ends are possible.
    7. Remember the pivot value in val value = nums[right].
    8. Track the boundary. var correctIndex = left is where the next value that is no larger than the pivot goes. Everything before it is already at most value.
    9. Scan. Loop i over left..right. When nums[i] <= value, swap it into position correctIndex and move the boundary one step.
    10. Return the pivot's index. The loop includes right on purpose. The pivot is itself at most value, so it is the last element moved to the front part and ends up at correctIndex - 1.
    11. Write swap. Copy nums[i] into temp, assign nums[j] to nums[i], then temp to nums[j]. Without temp, the first assignment would destroy a value.

    The solution in Kotlin

    class Solution {
    fun swap(nums: IntArray, i: Int, j: Int) {
        val temp = nums[i]
        nums[i] = nums[j]
        nums[j] = temp
    }

    fun partition(nums: IntArray, left: Int, right: Int): Int {
        val randomIndex = (left..right).random()
        swap(nums, randomIndex, right)
        val value = nums[right]
        var correctIndex = left
        for (i in left..right) {
            if (nums[i] <= value) {
                swap(nums, i, correctIndex)
                correctIndex++
            }
        }
        return correctIndex - 1
    }

    fun quickSort(nums: IntArray, left: Int, right: Int) {
        if (left >= right) {
            return
        }
        val pivot = partition(nums, left, right)
        quickSort(nums, left, pivot - 1)
        quickSort(nums, pivot + 1, right)
    }

    fun sort(nums: IntArray) {
        quickSort(nums, 0, nums.size - 1)
    }
}

    Kotlin details:

    • (left..right).random() is a standard-library function on ranges. It returns one random Int from the closed range, so with left == right it returns that index.
    • Return types. swap and quickSort declare no return type, which means Unit. partition declares : Int.
    • A bare return in a Unit function exits it early, as in the base case.
    • Parameters are read-only. You can't assign to left or right inside a function. The code never needs to, because it passes new bounds to the recursive calls.
    • Arrays are references. swap receives the same IntArray and changes it in place. That's why no function returns an array.

    A short trace

    Say the range is [3, 1, 3, 2, 5, 4] and the random pivot is the last element, 4. The loop moves 3, 1, 3 and 2 to the front in order, skips 5 and finally swaps the pivot into position 4:

    after the loop: [3, 1, 3, 2, 4, 5]   pivot index 4

    Everything left of index 4 is at most 4, and the 5 on the right is larger. Now quickSort handles [3, 1, 3, 2] and then [5].

    Complexity

    Time. A partition costs O(n) for a range of n elements. With a random pivot the splits are usually balanced enough that the recursion is about log n levels deep, so the expected time is O(n log n). The worst case is O(n²), but with a random pivot it is very unlikely.

    Space. Nothing is copied. The extra memory is the recursion stack, which is O(log n) for balanced splits.

    Edge cases and common mistakes

    • Empty array. quickSort(nums, 0, -1) hits left >= right and returns, so nothing happens.
    • Many equal values. The partition puts every value that is <= value on the left, so when all elements are equal the returned pivot index is always right, and each call shrinks the range by only one. Such input behaves like the O(n²) worst case, and with a very large array of equal values (200000 of them, for instance) the recursion is deep enough to end in a StackOverflowError. Handling duplicates better needs a three-way partition, which this lesson doesn't use.
    • Leaving the pivot in the middle. Moving it to the end first is what lets the loop treat all other elements the same way.
    • Recursing on pivot instead of pivot - 1 and pivot + 1. The range then never shrinks and the recursion doesn't end.
    • Sort stability. The swaps reorder equal elements, so this Quick Sort isn't stable. For plain integers that can't be seen.

    Testing

    • [3, 1, 3, 2, 5, 4] becomes [1, 2, 3, 3, 4, 5].
    • An empty array stays empty.
    • An array of 100000 numbers in scrambled order comes out sorted.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free