Created
June 5, 2014 01:02
-
-
Save fjcaetano/b0c00a889dc2a17efad9 to your computer and use it in GitHub Desktop.
Quicksort in Swift
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var randomNumbers = [42, 12, 88, 62, 63, 56, 1, 77, 88, 97, 97, 20, 45, 91, 62, 2, 15, 31, 59, 5] | |
func partition(v: Int[], left: Int, right: Int) -> Int { | |
var i = left | |
for j in (left + 1)..(right + 1) { | |
if v[j] < v[left] { | |
i += 1 | |
(v[i], v[j]) = (v[j], v[i]) | |
} | |
} | |
(v[i], v[left]) = (v[left], v[i]) | |
return i | |
} | |
func quicksort(v: Int[], left: Int, right: Int) { | |
if right > left { | |
let pivotIndex = partition(v, left, right) | |
quicksort(v, left, pivotIndex - 1) | |
quicksort(v, pivotIndex + 1, right) | |
} | |
} | |
quicksort(randomNumbers, 0, randomNumbers.count-1) | |
I tried a simpler example involving a bad array (string/number combination), like this one:
let myArr = [42, 12, "foo", 88]
println("Hello Swift World ", myArr)
... and when I do the xcrun swift bad.swift
I get a proper error message:
error: cannot convert the expression's type 'Array' to type 'ArrayLiteralConvertible'
... but when I do the same with Flávio's or Harlan's quicksort, I get no response at all, as far as I can see.
Just quickSort(&a, 0..a.count)
little bit improved with new swift grammar
func partition(inout dataList: [Int], low: Int, high: Int) -> Int {
var pivotPos = low
var pivot = dataList[low]
for var i = low + 1; i <= high; i++ {
if dataList[i] < pivot && ++pivotPos != i {
(dataList[pivotPos], dataList[i]) = (dataList[i], dataList[pivotPos])
}
}
(dataList[low], dataList[pivotPos]) = (dataList[pivotPos], dataList[low])
return pivotPos
}
func quickSort(inout dataList: [Int], left: Int, right: Int) {
if left < right {
var pivotPos = partition(&dataList, left, right)
quickSort(&dataList, left, pivotPos - 1)
quickSort(&dataList, pivotPos + 1, right)
}
}
var dataList = [42, 12, 88, 62, 63, 56, 1, 77, 88, 97, 97, 20, 45, 91, 62, 2, 15, 31, 59, 5]
quickSort(&dataList, 0, dataList.count - 1)
This is your solution with a bit modification for Swift 5:
var randomNumbers = [42, 12, 88, 62, 63, 56, 1, 77, 88, 97, 97, 20, 45, 91, 62, 2, 15, 31, 59, 5]
// MARK: - Solution 1 : Naive
func quicksort1<T: Comparable>(_ list: [T]) -> [T] {
if list.count <= 1 {
return list
}
let pivot = list.randomElement() ?? list[0]
var smallerList = [T]()
var equalList = [T]()
var biggerList = [T]()
for x in list {
switch x {
case let x where x < pivot:
smallerList.append(x)
case let x where x == pivot:
equalList.append(x)
case let x where x > pivot:
biggerList.append(x)
default:
break
}
}
return quicksort1(smallerList) + equalList + quicksort1(biggerList)
}
quicksort1(randomNumbers)
// solution 1 with array extension
extension Array where Element: Comparable {
func quicksort1() -> [Element] {
let list = self
if list.count <= 1 {
return list
}
let pivot = list.randomElement() ?? list[0]
var smallerList = [Element]()
var equalList = [Element]()
var biggerList = [Element]()
for x in list {
switch x {
case let x where x < pivot:
smallerList.append(x)
case let x where x == pivot:
equalList.append(x)
case let x where x > pivot:
biggerList.append(x)
default:
break
}
}
return smallerList.quicksort1() + equalList + biggerList.quicksort1()
}
}
randomNumbers.quicksort1()
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Tried to quantify @harlanhaskins's "dramatically": The overhead seems to be quite considerable, given a larger list of arcr4andom UInt32s. At 1M entries, the filter variant is roughly 26% slower (40.078sec vs 31.734sec), at 10M roughly 35% (456.69sec vs 337.18sec). For 1k entries, both implementations are in the tens of milliseconds.