Quick Sort

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. source 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 and high 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 to low. For each j from low to high (not inclusive), compare if the current element is less than or equal to the pivot: 3.1 Swap the element at index i with the element at index j. 3.2 Increment i by 1. Swap the element at index i with the last element. Return i. Time/Space complexity Time complexity: O(N^2) Space complexity: O(N) ...