Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Quicksort - the only use for partition(by:) I could find
import Foundation
extension Array where Element: Comparable {
mutating func quickSort() {
self[self.indices].quickSort()
}
}
extension ArraySlice where Element: Comparable {
mutating func quickSort() {
guard self.count > 1 else { return }
let pivotValue = self[startIndex]
let pivotIndex = self.partition(by: { $0 >= pivotValue })
if (pivotIndex == startIndex) {
self[index(after: startIndex)..<self.endIndex].quickSort()
} else {
self[self.startIndex..<pivotIndex].quickSort()
self[pivotIndex..<self.endIndex].quickSort()
}
}
}
for _ in 0..<100 {
var a = (0..<10).map({ _ in arc4random_uniform(100) })
var copy = a
a.quickSort()
if a != copy.sorted() {
print("failed!")
print(a)
break
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.