Like merge sort, quicksort is implemented with the idea of grouping.
The most important part of quicksort is the choice of pivot, which is how we group the array. Support the array is divided into three parts: [less than the pivot element | | protection is greater than the pivot element].
In this article, we will choose two types of grouping to implement quicksort: 1) Lomuto partitioning, with the last element as the fulcrum; 2) Hoare partition, with the first element as the fulcrum.
Lomuto division
Divide the principle
The Lomuto partition is based on the last element.
Let’s take the following out-of-order array: [13, 2, 5, 8, 10, 32, 10].
First, we’ll name the index of the first element low and the index of the last element high; I is used to record the number of elements less than or equal to the fulcrum after a round of partitioning, and j is the current traversal position of the array. The fulcrum is the last element 10. After selecting this fulcrum, the fulcrum will remain unchanged for the current round.
0 1 2 3 4 5 6
[ 13, 2, 5, 8, 10, 32, 10]
low high
i
j
Copy the code- The first element
13Greater than the pivot10.iAnd the value of phi doesn’t change,j加1, the results are:
0 1 2 3 4 5 6
[ 13, 2, 5, 8, 10, 32, 10]
low high
i
j
Copy the code- The second element
2Less than the pivot10The swapi和jThe corresponding element,i加1.j加1, the results are:
0 1 2 3 4 5 6
[ 2, 13, 5, 8, 10, 32, 10]
low high
i
j
Copy the code- The third element
5Less than the pivot10The swapi和jThe corresponding element,i加1.j加1, the results are:
0 1 2 3 4 5 6
[ 2, 5, 13, 8, 10, 32, 10]
low high
i
j
Copy the code- The fourth element
8Less than the pivot10The swapi和jThe corresponding element,i加1.j加1, the results are:
0 1 2 3 4 5 6
[ 2, 5, 8, 13, 10, 32, 10]
low high
i
j
Copy the code- Fifth element
10Is equal to the pivot10The swapi和jThe corresponding element,i加1.j加1, the results are:
0 1 2 3 4 5 6
[ 2, 5, 8, 10, 13, 32, 10]
low high
i
j
Copy the code- Sixth element
32Greater than the pivot10.iThe same,jIt already points to the last element in the array other than the fulcrum. The result is:
0 1 2 3 4 5 6
[ 2, 5, 8, 10, 13, 32, 10]
low high
i
Copy the code- The fulcrum with
iThe corresponding elements switch positions, and the partition of the first round ends here, and all the elements to the left of I are less than or equal to the fulcrum10; The elements to the right of I, except for the last element, are unsorted, and there’s only one because the array is short32If you start the array by adding one more element that is larger than the fulcrum11, then11It’s also in this unsorted range. The result is:
0 1 2 3 4 5 6
[ 2, 5, 8, 10, 10, 32, 13]
low high
i
Copy the codePartition code implementation
func lomutoPartition<T: Comparable> (_ array: inout [T].low: Int.high: Int) -> Int {
// The last element is the fulcrum
let pivot = array[high]
// The initial value of I is low
var i = low
for j in low..<high {
if array[j] < = pivot { // The value currently traversed is less than or equal to the fulcrum
array.swapAt(i, j) // Swap values for I and j
i + = 1 / / I + 1}}// Swap fulcrum and I for each other
array.swapAt(i, high)
return i
}
Copy the codeThe sorting implementation of Lomuto partitions
Once the partition is complete, the code to implement the sorting is very simple. The code is as follows:
func lomutoQuicksort<T: Comparable> (_ array: inout [T].low: Int.high: Int) {
guard low < high else {
return
}
let pivot = lomutoPartition(&array, low: low, high: high)
lomutoQuicksort(&array, low: low, high: pivot - 1)
lomutoQuicksort(&array, low: pivot + 1, high: high)
}
Copy the codeAfter testing, the results are correct:
var list = [13.2.5.8.10.32.10]
lomutoQuicksort(&list, low: 0, high: list.count - 1)
print(list)
/ / the result:
[2.5.8.10.10.13.32]
Copy the codeHoare division
Divide the principle
The Hoare partition is based on the first element.
Let’s use that array again: [13, 2, 5, 8, 10, 32, 10].
First, we take the first element 13 as the fulcrum. After selecting this fulcrum, we divide the fulcrum unchanged in the current round. The initial value of I is the minimum index minus 1, and the initial value of j is the maximum index plus 1. Keep moving I to the center until the value of I is not less than the fulcrum; Keep moving j to the center until j is no greater than the fulcrum; Then swap the values for I and j; Repeat the above steps until I and J overlap, then proceed to the next round of partitioning.
0 1 2 3 4 5 6
[ 13, 2, 5, 8, 10, 32, 10]
i j
Copy the code- will
iYou keep moving to the center,iMove to the corresponding element13Is not less than the fulcrum13, soiThe value of is temporarily0; willjYou keep moving to the center,jMove to the corresponding element10, not greater than the fulcrum13, sojThe value of is temporarily6That will bei和jThe corresponding values are swapped, and the result is as follows:
0 1 2 3 4 5 6
[ 10, 2, 5, 8, 10, 32, 13]
i j
Copy the code- will
iI’m going to keep moving to the center,iMove to the corresponding element32Is not less than the fulcrum13, soiThe value of is temporarily5; willjYou keep moving to the center,jMove to the corresponding element10, not greater than the fulcrum13, sojThe value of is temporarily4; Here are the results:
0 1 2 3 4 5 6
[ 10, 2, 5, 8, 10, 32, 13]
i
j
Copy the codeThe value of I is 5, and the value of j is 4, which means they have overlapped. So everything before j is less than or equal to the fulcrum, so the first partition is done.
Partition code implementation
func hoarePartition<T: Comparable> (_ array: inout [T].low: Int.high: Int) -> Int {
// Use the first element as the fulcrum
let pivot = array[low]
// Move I 1 bit to the left to facilitate the use of the repeat while statement below
var i = low - 1
// // moves j 1 bit to the left to facilitate the repeat while statement below
var j = high + 1
while true {
// 'I += 1' is executed at least once anyway. If the corresponding value of I is less than the fulcrum, continue to move to the right
repeat { i + = 1 } while array[i] < pivot
// 'j -= 1' will be executed at least once anyway. If the value corresponding to I is greater than the fulcrum, continue to move left
repeat { j - = 1 } while array[j] > pivot
if i < j { // I is less than j, swap their values
array.swapAt(i, j)
} else { // I and j have overlapped, return j
return j
}
}
}
Copy the codeSorting implementation of Hoare partition
func hoareQuicksort<T: Comparable> (_ array: inout [T].low: Int.high: Int) {
guard low < high else {
return
}
let pivot = hoarePartition(&array, low: low, high: high)
hoareQuicksort(&array, low: low, high: pivot)
hoareQuicksort(&array, low: pivot + 1, high: high)
}
Copy the codeAfter testing, the results are correct:
var list = [13.2.5.8.10.32.10]
hoareQuicksort(&list, low: 0, high: list.count - 1)
print(list)
/ / the result:
[2.5.8.10.10.13.32]
Copy the codeWorst case analysis
We just saw that: 1) Lomuto is partitioned, with the last element as the fulcrum; 2) Hoare partition, with the first element as the fulcrum.
But given this array: [5, 4, 3, 2, 1], if you use lomuto partition, the fulcrum is the last element 1, and after the first partition, you get the following:
Less than fulcrum: [] equal to fulcrum: [1] greater than fulcrum: [5, 4, 3, 2]Copy the codeFor an array like this, sorting would be very inefficient, with time complexity of O(n^2). So neither the first element nor the last element is a very ideal fulcrum. The ideal fulcrum is to divide the array evenly into two parts.
We can first approximate the middle value of an array by doing the following:
func medianPivot<T: Comparable> (_ array: inout [T].low: Int.high: Int) -> Int {
let center = (low + high) / 2
if array[low] > array[center] {
array.swapAt(low, center)
}
if array[low] > array[high] {
array.swapAt(low, high)
}
if array[center] > array[high] {
array.swapAt(center, high)
}
return center
}
Copy the codeArray [center] >= array[low]; Array [high] >= array[low]; After the third if is executed, array[high] >= array[center] is satisfied. So after all three ifs, we get array[high] >= array[center] >= array[low], and we can roughly put the middle of the array in the middle of the array.
Optimize the Lomuto partition with the following results:
func medianQuicksort<T: Comparable> (_ array: inout [T].low: Int.high: Int) {
guard low < high else {
return
}
// Get the position of the median
let center = medianPivot(&array, low: low, high: high)
// By swapping the median and the last element, the lomuto partition can use the median as the fulcrum
array.swapAt(center, high)
let pivot = lomutoPartition(&array, low: low, high: high)
lomutoQuicksort(&array, low: low, high: pivot - 1)
lomutoQuicksort(&array, low: pivot + 1, high: high)
}
Copy the codeAfter testing, the results are correct:
var list = [5.4.3.2.1]
hoareQuicksort(&list, low: 0, high: list.count - 1)
print(list)
/ / the result:
[1.2.3.4.5]
Copy the codeNon-recursive implementation
The previous methods used recursion, if not recursion, we can use Stack to simulate recursion, because recursion calls form a Stack. If you’re not familiar with Stack, check out the link to learn more about Stack.
The implementation code is as follows:
func nonrecursiveQuicksort<T: Comparable> (_ array: inout [T].low: Int.high: Int) {
guard low < high else {
return
}
var stack = Stack<Int>()
stack.push(low)
stack.push(high)
while !stack.isEmpty {
guard let end = stack.pop(),
let start = stack.pop() else {
continue
}
let pivot = lomutoPartition(&array, low: start, high: end)
if (pivot - 1) > start {
stack.push(start)
stack.push(pivot - 1)}if (pivot + 1) < end {
stack.push(pivot + 1)
stack.push(end)
}
}
}
Copy the codeAfter testing, the results are correct:
var list = [13.2.5.8.10.32.10]
nonrecursiveQuicksort(&list, low: 0, high: list.count - 1)
print(list)
/ / the result:
[2.5.8.10.10.13.32]
Copy the codeWelcome to join my Swift development group: 536353151.
Complete code >>
The resources
Data Structures and Algorithms in Swift — Raywenderlich.com. Click on the link to buy the original.