Quick Sort Algorithms in Swift

1. Introduction

Quick Sort is a divide and conquer sorting algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

2. Implementation Steps

1. Choose a 'pivot' element from the array and partition the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

2. Recursively apply the above steps to the sub-arrays.

3. The base case of the recursion is arrays of size 0 or 1, which never need to be sorted.

3. Implementation in Swift

func quickSort(_ arr: inout [Int], _ low: Int, _ high: Int) {
    if low < high {
        // Find pivot element such that element smaller than pivot are on the left
        // and elements greater than pivot are on the right
        let pivot = partition(&arr, low, high)
        // Recursively sort elements before and after pivot
        quickSort(&arr, low, pivot - 1)
        quickSort(&arr, pivot + 1, high)
    }
}
func partition(_ arr: inout [Int], _ low: Int, _ high: Int) -> Int {
    let pivot = arr[high]
    var i = low - 1
    for j in low..<high {
        if arr[j] < pivot {
            i += 1
            (arr[i], arr[j]) = (arr[j], arr[i])
        }
    }
    (arr[i + 1], arr[high]) = (arr[high], arr[i + 1])
    return i + 1
}
// Usage:
var numbers = [10, 80, 30, 90, 40, 50, 70]
quickSort(&numbers, 0, numbers.count - 1)
print(numbers)

Output:

[10, 30, 40, 50, 70, 80, 90]

Explanation:

1. The primary function quickSort begins by checking if the base case has been reached (i.e., if the segment of the array to be sorted contains one or zero elements). If not, it proceeds to partition the segment.

2. The partition function selects the last element as the pivot. All elements smaller than the pivot are moved to its left, and all the greater elements to its right.

3. The pivot is then placed in its correct position, which is the point where the array gets divided. The index of the pivot is returned.

4. The quickSort function is then recursively applied to the sub-arrays formed by dividing the array at the pivot.

Note: The choice of the pivot selection and partitioning schemes greatly affects the algorithm's performance. This simple version always picks the last element as a pivot, which works well with many real-world data sets.