【 Data structure and algorithm - Swift implementation 】

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 element13Greater 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 element2Less 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 element5Less 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 element8Less 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 element10Is 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 element32Greater 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 withiThe 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 code

Partition 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 code

The 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 code

After 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 code

Hoare 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

williYou 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

williI’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 code

The 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 code

Sorting 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 code

After 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 code

Worst 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 code

For 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 code

Array [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 code

After 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 code

Non-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 code

After 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 code

Welcome 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.

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

【 Data structure and algorithm – Swift implementation 】

Lomuto division

Divide the principle

Partition code implementation

The sorting implementation of Lomuto partitions

Hoare division

Divide the principle

Partition code implementation

Sorting implementation of Hoare partition

Worst case analysis

Non-recursive implementation

Complete code >>

The resources

【 Data structure and algorithm – Swift implementation 】

Lomuto division

Divide the principle

Partition code implementation

The sorting implementation of Lomuto partitions

Hoare division

Divide the principle

Partition code implementation

Sorting implementation of Hoare partition

Worst case analysis

Non-recursive implementation

Complete code >>

The resources

Related Posts

Custom shape button implementation

IOS Notes Runtime API

Xcode 9 is a new feature in iOS 11.