Problem overview
The method sort receives an Array[Int] called nums and sorts it in ascending order in place, using Quick Sort. It returns Unit. For [3, 1, 3, 2, 5, 4] the array becomes [1, 2, 3, 3, 4, 5].
The target is O(n log n) time and O(log n) extra space. For Quick Sort these are expected costs with a random pivot, not guarantees for every possible run.
Approach: partition around a pivot, then recurse
Quick Sort picks one element, the pivot, and rearranges the range so that everything less than or equal to the pivot sits before it and everything greater sits after it. That step is called partitioning. After it, the pivot is in its final sorted position, and the two sides can be sorted independently. Each side is a smaller instance of the same problem, so recursion handles them.
Merge Sort does its hard work after the recursive calls, when it merges. Quick Sort does it before them, when it partitions, and needs no buffer, which is why its extra space is only the call stack.
The choice of pivot decides the speed. If every pivot splits its range roughly in half, the depth is about log2(n) and the total time is O(n log n). If the pivot is always the smallest or largest element, each call removes only one element and the time becomes O(n²). A pivot at a fixed position, such as the last element, is exactly the largest on already sorted input. A random pivot makes that bad luck very unlikely on any input.
Step by step
- Start the recursion with
quickSort(nums, 0, nums.length - 1). Both bounds are inclusive. - Declare
quickSort(nums, left, right)returningUnit. Arrays are passed by reference, so sorting inside the method changes the caller's array. - Base case: if
left >= right, the range has at most one element and is already sorted, so return. - Partition with
val pivot = partition(nums, left, right), which returns the pivot's final index. - Sort the left part,
lefttopivot - 1, and then the right part,pivot + 1toright. The pivot is left out because it is already in place. - Write
partition. First pickrandomIndexasleftplusscala.util.Random.nextInt(right - left + 1).nextInt(n)returns 0 to n - 1, and the range hasright - left + 1elements. - Move the pivot to the end with
swap(nums, randomIndex, right)and save its value inval value = nums(right). - Track the boundary.
var correctIndex = leftis where the next element that is at mostvaluebelongs. Everything before it already qualifies. - Scan
ifromlefttorightinclusive. Whenevernums(i) <= value, swap it into positioncorrectIndexand incrementcorrectIndex. - Return
correctIndex - 1. The scan reaches the pivot last, and it swaps it to the end of the small elements, so the pivot sits just beforecorrectIndex. - Write
swapwith a temporaryval, so the first assignment doesn't destroy a value that is still needed.
The solution in Scala
class Solution {
def swap(nums: Array[Int], i: Int, j: Int): Unit = {
val temp = nums(i)
nums(i) = nums(j)
nums(j) = temp
}
def partition(nums: Array[Int], left: Int, right: Int): Int = {
val randomIndex = left + scala.util.Random.nextInt(right - left + 1)
swap(nums, randomIndex, right)
val value = nums(right)
var correctIndex = left
for (i <- left to right) {
if (nums(i) <= value) {
swap(nums, i, correctIndex)
correctIndex += 1
}
}
correctIndex - 1
}
def quickSort(nums: Array[Int], left: Int, right: Int): Unit = {
if (left >= right) {
return
}
val pivot = partition(nums, left, right)
quickSort(nums, left, pivot - 1)
quickSort(nums, pivot + 1, right)
}
def sort(nums: Array[Int]): Unit = {
quickSort(nums, 0, nums.length - 1)
}
}
Scala details:
- The last expression is the result.
partitionends withcorrectIndex - 1, with noreturn. InquickSort, the barereturnis only an early exit. left to rightis inclusive. That is deliberate: the pivot atrightmust be visited. Because it is at most itself, it is swapped into the small side last.- No
++. UsecorrectIndex += 1. - Two assignments and a temporary.
nums(i) = nums(j)uses theupdatemethod of arrays behind the scenes, andtempkeeps the oldnums(i)alive. - A walk-through. If the random pivot is the 4 in
[3, 1, 3, 2, 5, 4], it is swapped to the end (it is already there). Then 3, 1, 3 and 2 are each at most 4 and stay where they are, 5 is skipped, and the 4 is swapped into index 4.correctIndexends at 5, the function returns 4, and the 5 is to the right of the 4.
Complexity
Time: O(n log n) expected. One partition of a range of size m costs O(m). With random pivots the ranges shrink geometrically on average, so a level of recursion costs O(n) in total and there are about log n levels. The worst case, with unlucky pivots, is O(n²).
Space: O(log n) expected, for the call stack. The partition works in place.
Edge cases and common mistakes
- Empty array. The call is
quickSort(nums, 0, -1), andleft >= rightreturns at once. - Already sorted input. A random pivot keeps it fast. An array of the numbers 0 to 99,999 in order sorts without trouble.
- Many equal values. Because the test is
nums(i) <= value, all equal elements go to the left side, so for an array in which every element is the same, the pivot always ends at indexright. Each call then recurses on a range only one element shorter, which is quadratic work and a recursion as deep as the array. An array of 20,000 equal values fails with aStackOverflowError. A three-way partition (less, equal, greater) avoids the problem. - Negative numbers and duplicates.
[9, -3, 0, -3, 7, 1, 1]becomes[-3, -3, 0, 1, 1, 7, 9]. - Wrong random range.
nextInt(right - left)could never pick the last index of the range, because the range hasright - left + 1elements. - Recursing on the pivot. Using
pivotinstead ofpivot - 1orpivot + 1can leave a range that never shrinks. - Not stable. The swaps reorder equal elements, which only matters when sorting records by a key.
Testing
[3, 1, 3, 2, 5, 4]becomes[1, 2, 3, 3, 4, 5].[]stays[].[9, -3, 0, -3, 7, 1, 1]becomes[-3, -3, 0, 1, 1, 7, 9].- 200,000 random integers come out in non-decreasing order.
