Skip to content

Instantly share code, notes, and snippets.

@coreyd303
Last active September 4, 2020 22:55
Show Gist options
  • Save coreyd303/5423a6e443a140211ecbd58ca5b22f38 to your computer and use it in GitHub Desktop.
Save coreyd303/5423a6e443a140211ecbd58ca5b22f38 to your computer and use it in GitHub Desktop.
import Foundation
func quickSort(array: inout [Int], low: Int, high: Int) {
// if the high index value is greater than the low index value we need to partition and sort
if high > low {
// determine our pivot index by generating partitions
let pi = partition(array: &array, low: low, high: high)
// recursively pass our upper and lower partitions back into quickSort using the new pivot index
quickSort(array: &array, low: low, high: pi - 1)
quickSort(array: &array, low: pi + 1, high: high)
}
// the array is in order the func will cease
}
func partition(array: inout [Int], low: Int, high: Int) -> Int {
var i = low
// loop through the partition of the array
for j in (low + 1)..<(high + 1) {
// if the value at index j is less than the value at the lower end of our partition
// we increment our pivot index and swap the values
if array[j] < array[low] {
i += 1
array.swapAt(i, j)
}
}
// once the loop is done, place pivot value at the first position in the array
array.swapAt(i, low)
// return the pivot index
return i
}
var numbers = [Int]()
for _ in 0..<20 {
numbers.append(Int(arc4random_uniform(UInt32(1000))))
}
print(numbers) // [508, 581, 858, 660, 971, 158, 247, 363, 562, 87, 498, 925, 766, 165, 279, 195, 302, 516, 939, 4]
quickSort(array: &numbers, low: 0, high: numbers.count - 1)
print(numbers) // [4, 87, 158, 165, 195, 247, 279, 302, 363, 498, 508, 516, 562, 581, 660, 766, 858, 925, 939, 971]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment