Introduction
The quick sort is an efficient sorting algorithm commonly used widely in production. Quick sort is a divide-and-conquer algorithm. It works by selecting a pivot from the array and partitioning the other elements into two subarrays.
Code example
// Sorts a (portion of an) array, divides it into partitions, then sorts those
func quickSort(array: inout [Int], low: Int, high: Int) {
// Ensure indices are in correct order
if low < high {
// Partition array and get the pivot index
let p = partition(array: &array, low: low, high: high)
// Sort the two partitions
quickSort(array: &array, low: low, high: p - 1) // Left side of pivot
quickSort(array: &array, low: p + 1, high: high) // Right side of pivot
}
}
// Divides array into two partitions
func partition(array: inout [Int], low: Int, high: Int) -> Int {
let pivot = array[high] // Choose the last element as the pivot
// Temporary pivot index
var i = low
for j in low ..< high {
// If the current element is less than or equal to the pivot
if array[j] <= pivot {
// Swap the current element with the element at the temporary pivot index
let tmp = array[i]
array[i] = array[j]
array[j] = tmp
// Move the temporary pivot index forward
i += 1
}
}
// Swap the pivot with the last element
let tmp = array[i]
array[i] = array[high]
array[high] = tmp
return i
}
Implementation
quickSort
- Ensure that the
low
andhigh
indices are in the correct order. - Partition the input list using the
partition
function. - Recursively call
quickSort
on the left side of the pivot. - Recursively call
quickSort
on the right side of the pivot.
partition
- Choose the last element as the pivot.
- Set
i
tolow
. - For each
j
fromlow
tohigh
(not inclusive), compare if the current element is less than or equal to the pivot:
3.1 Swap the element at indexi
with the element at indexj
.
3.2 Incrementi
by1
. - Swap the element at index
i
with the last element. - Return
i
.
Time/Space complexity
Time complexity: O(N^2)
Space complexity: O(N)