Swift Sorts IX: Quicksort Improvements
Even though it’s fast, Quicksort can be made faster. We’ll consider two simple ways to increase it’s speed in this post.
This is the last discussion of Quicksort before we move on the the Swift system sort, which is called Timsort. There’s a method to the order of presentation of these sorts. Timsort is remarkably similar to Quicksort and utilizes improvements that are similar to what we’ll discuss today.
For Quicksort, when the array is anywhere between 10 and 20 if we default to Insertion sort we can improve the running time by 20%.
This is done as follows:
enum sortInt: Int {
case cutoff = 20
}
func quickSort(array: [Double]) -> [Double] {
var a = knuthShuffle(a: array)
quickSort(a: &a, lo: 0, hi: a.count – 1)
return a
}
func quickSort(a: inout [Double], lo: Int, hi: Int) {
if hi <= lo {
return
}
if hi <= lo + sortInt.cutoff.rawValue – 1 {
insertionSort(a: &a, lo: lo, hi: hi)
}
let j = quickSortPartition(a: &a, lo: lo, hi: hi)
quickSort(a: &a, lo: lo, hi: j – 1)
quickSort(a: &a, lo: j+1, hi: hi)
}
public func insertionSort(a: inout [Double], lo: Int, hi: Int) {
let c = a[safe: lo, _: hi]
var b = Array(c)
for i in 0..<b.count {
for j in (0…i).reversed() {
if j-1 >= 0,b[j] < b[j-1] {
b = exchange(a: b, i: j, j: j-1)
} else {
break
}
}
}
}
extension Array where Element : Equatable {
public subscript(safe bounds: Range<Int>) -> ArraySlice<Element> {
if bounds.lowerBound > count { return [] }
let lower = Swift.max(0, bounds.lowerBound)
let upper = Swift.max(0, Swift.min(count, bounds.upperBound))
return self[lower..<upper]
}
public subscript(safe lower: Int?, _ upper: Int?) -> ArraySlice<Element> {
let lower = lower ?? 0
let upper = upper ?? count
if lower > upper { return [] }
return self[safe: lower..<upper]
}
}
func quickSortPartition(a: inout [Double], lo: Int, hi: Int) -> Int {
var i = lo
var j = hi + 1
while(true) {
i += 1
while (a[i] < a[lo]) {
if i == hi {
break
}
i += 1
}
j -= 1
while a[lo] < a[j] {
if j == lo {
break
}
j -= 1
}
if i >= j {
break
}
a = exchange(a: a, i: i, j: j)
}
a = exchange(a: a, i: lo, j: j)
return j
}
Here we’ve added an insertion sort modification that merely takes a slice of the array at the indicated endpoints and creates a new array from it. Then it does the insertion sort of the new array. The point is that for small arrays, Insertion sort is more efficient than something like Quicksort, which has considerably more overhead.
This is accomplished with the line:
if hi <= lo + sortInt.cutoff.rawValue – 1 {
insertionSort(a: &a, lo: lo, hi: hi)
}
A second improvement is to start with a better partition point. This increases our efficiency another 10 percent.
enum sortInt: Int {
case cutoff = 20
}
func quickSort(array: [Double]) -> [Double] {
var a = knuthShuffle(a: array)
quickSort(a: &a, lo: 0, hi: a.count – 1)
return a
}
func quickSort(a: inout [Double], lo: Int, hi: Int) {
if hi <= lo {
return
}
if hi <= lo + sortInt.cutoff.rawValue – 1 {
insertionSort(a: &a, lo: lo, hi: hi)
}
let m = Int([lo, lo + (hi – lo)/2, hi].median() ?? 0)
a = exchange(a: a, i: lo, j: m)
let j = quickSortPartition(a: &a, lo: lo, hi: hi)
quickSort(a: &a, lo: lo, hi: j – 1)
quickSort(a: &a, lo: j+1, hi: hi)
}
extension Array where Element == Int {
func median() -> Double? {
guard count > 0 else { return nil }
let sortedArray = self.sorted()
if count % 2 != 0 {
return Double(sortedArray[count/2])
} else {
return Double(sortedArray[count/2] + sortedArray[count/2 – 1]) / 2.0
}
}
}
public func insertionSort(a: inout [Double], lo: Int, hi: Int) {
let c = a[safe: lo, _: hi]
var b = Array(c)
for i in 0..<b.count {
for j in (0…i).reversed() {
if j-1 >= 0,b[j] < b[j-1] {
b = exchange(a: b, i: j, j: j-1)
} else {
break
}
}
}
}
extension Array where Element : Equatable {
public subscript(safe bounds: Range<Int>) -> ArraySlice<Element> {
if bounds.lowerBound > count { return [] }
let lower = Swift.max(0, bounds.lowerBound)
let upper = Swift.max(0, Swift.min(count, bounds.upperBound))
return self[lower..<upper]
}
public subscript(safe lower: Int?, _ upper: Int?) -> ArraySlice<Element> {
let lower = lower ?? 0
let upper = upper ?? count
if lower > upper { return [] }
return self[safe: lower..<upper]
}
}
func quickSortPartition(a: inout [Double], lo: Int, hi: Int) -> Int {
var i = lo
var j = hi + 1
while(true) {
i += 1
while (a[i] < a[lo]) {
if i == hi {
break
}
i += 1
}
j -= 1
while a[lo] < a[j] {
if j == lo {
break
}
j -= 1
}
if i >= j {
break
}
a = exchange(a: a, i: i, j: j)
}
a = exchange(a: a, i: lo, j: j)
return j
}
In this case, we’re adding the calculation of the median of three sampled values:
let m = Int([lo, lo + (hi – lo)/2, hi].median() ?? 0)
a = exchange(a: a, i: lo, j: m)
And we’ve added the code to calculate the median.
Altogether, with these two improvements, we’ve increased the efficiency of Quicksort somewhere between 10% and 30%.