Problem overview
The method sort receives an array of integers, nums, as an inout parameter and must sort it in ascending order with Quick Sort. The statement asks for O(n log n) time and O(log n) extra space. The sorted result replaces the contents of the caller's array.
For nums = [3, 1, 3, 2, 5, 4] the array becomes [1, 2, 3, 3, 4, 5].
Approach: partition around a pivot, then sort both sides
Quick Sort picks one element, the pivot, and rearranges the range so that every element not larger than the pivot comes before it and every larger element after it. This is partitioning. The pivot is then in its final position, and nothing has to cross it again. What is left is two smaller sorting problems, one on each side of the pivot, solved with the same method.
Unlike Merge Sort, Quick Sort works inside the array and needs no second array. The extra memory is only the recursion stack.
The speed depends on the pivot. A pivot near the middle halves the problem, giving about log₂ n levels of O(n) partitioning work each, so O(n log n). A pivot that is always the smallest or largest value peels off one element per level and costs O(n²). Always picking the first or last element makes that happen on already sorted input. The lesson picks a random index, so no particular input is reliably bad, and O(n log n) holds in expectation.
Take [3, 1, 3, 2, 5, 4] with 3 as the pivot value. Four elements (3, 1, 3, 2) are not larger than 3, so after partitioning they fill indices 0 to 3, the pivot's final index is 3, and 5 and 4 sit to its right. Both sides are then sorted the same way.
Step by step
- Start the recursion from
sortwithquickSort(&nums, 0, nums.count - 1), which covers the whole array. - Declare
quickSortwith aninout [Int]and the boundsleftandright, without labels. - Base case: if
left >= right, the range has at most one element, so return. This also covers the empty ranges that come frompivot - 1andpivot + 1. - Partition the range and store the pivot's final index in
pivot. - 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. It takes the same three parameters and returns anInt. - Choose a random pivot with
Int.random(in: left...right)and swap it to the end of the range, so the loop that follows can treat all other elements uniformly. - Remember the pivot value as
value, and startcorrectIndexatleft. Everything beforecorrectIndexis already not larger thanvalue. - Scan from
leftthroughrightinclusive. Each element that is<= valueis swapped tocorrectIndex, andcorrectIndexgrows by one. - Return
correctIndex - 1. The pivot sits at the end and is<= value, so it is the last element moved into the left group, just beforecorrectIndex. - Write
swap, which exchanges two elements through a temporary constant.
The solution in Swift
class Solution {
func swap(_ nums: inout [Int], _ i: Int, _ j: Int) {
let temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
func partition(_ nums: inout [Int], _ left: Int, _ right: Int) -> Int {
let randomIndex = Int.random(in: left...right)
swap(&nums, randomIndex, right)
let value = nums[right]
var correctIndex = left
for i in left...right {
if nums[i] <= value {
swap(&nums, i, correctIndex)
correctIndex += 1
}
}
return correctIndex - 1
}
func quickSort(_ nums: inout [Int], _ left: Int, _ right: Int) {
if left >= right {
return
}
let pivot = partition(&nums, left, right)
quickSort(&nums, left, pivot - 1)
quickSort(&nums, pivot + 1, right)
}
func sort(_ nums: inout [Int]) {
quickSort(&nums, 0, nums.count - 1)
}
}
The Swift details worth a closer look:
inoutand&. Swift parameters are constants unless markedinout, and each call must pass the array with&. Without it the compiler reportspassing value of type '[Int]' to an inout parameter requires explicit '&'.- A method called
swap. Swift also has a globalswap(_:_:)function. Inside the class, the callswap(&nums, i, j)finds the class's own method first, so the three-argument version above is the one that runs. The global function takes twoinoutvalues and would need different code. - Closed ranges.
Int.random(in: left...right)and theforloop overleft...rightboth includeright. The loop visits the pivot last on purpose, and moving it into the left group is what puts it in its final position. - Swapping an element with itself. When
iequalscorrectIndex,swap(&nums, i, i)changes nothing and is harmless. - No
++. Swift has no increment operator, so the lesson writescorrectIndex += 1. - Empty ranges.
quickSortmay be called withrightsmaller thanleft, such aspivot - 1when the pivot is atleft. The base case catches it beforeleft...rightis ever formed. A closed range with a lower bound above its upper bound would crash the program.
Complexity
Time: O(n log n) expected. One partition touches each element of its range once. With a random pivot the ranges shrink geometrically on average, giving about log n levels, so the total is O(n log n). The worst case is still O(n²), but the random choice makes it very unlikely on any input.
Space: O(log n) expected. Sorting happens in place. The only extra memory is the recursion stack, whose depth follows the number of levels, about log n when pivots are reasonably balanced.
Edge cases and common mistakes
- Empty and single-element arrays. For an empty array the first call is
quickSort(&nums, 0, -1), which returns at once becauseleft >= right. A single element returns the same way. - Duplicates.
[2, 2, 2, 1, 1, 9, -4]becomes[-4, 1, 1, 2, 2, 2, 9]. Because the test is<=, elements equal to the pivot go to its left side. With many equal values the pivot ends up at the right end of its group, so the partitions are lopsided: an array of identical values costsO(n²)time and a recursion depth of aboutn. Sorting an array of twenty thousand equal values still finishes, but very large inputs of that kind could exhaust the stack. - Skipping the swap to the end. The loop assumes the pivot is the last element. If it stays at its random position, the final
correctIndex - 1no longer points at it. - Including the pivot in a recursive call. Recursing on
left...pivotkeeps a range the same size when the pivot is atright, and the recursion doesn't end. - Scanning only to
right - 1. That leaves the pivot unplaced, and the returned index is then wrong.
Testing
[3, 1, 3, 2, 5, 4]gives[1, 2, 3, 3, 4, 5].[]gives[].[2, 2, 2, 1, 1, 9, -4]gives[-4, 1, 1, 2, 2, 2, 9].
