Swiftでクイックソートプログラム。
quicksort.swift
//: Playground - noun: a place where people can play
import UIKit
var list = [Int]()
for i in 1...10000 {
var randomNum = Int(arc4random()%10000)
list.append(randomNum)
}
//quicksort ex1
func quicksort1(list:[Int]) -> [Int]{
//無限ループを防ぐ
if list.count == 0 {
return []
}
//pivotを選択
let pivotValue = list[0]
//filterを用いる。closerで条件を書く。
let smaller = list.filter({$0 < pivotValue})
let greater = list.filter({$0 > pivotValue})
return quicksort1(smaller) + Array(arrayLiteral:pivotValue) + quicksort1(greater)
}
//Benchmark
var d1 = NSDate()
quicksort1(list)
var d2 = NSDate()
var time = Float(d2.timeIntervalSinceDate(d1))
println("\(time)")
//quicksort ex2
func quicksort2(list:[Int]) -> [Int]{
if list.count == 0 {
return []
}
let pivotValue = list[0]
//pivotを配列から取り除く
let listStripped = list.count > 1 ? list[1...(list.count-1)] : []
//「.filter」だとなぜかエラーを吐く
// let smaller = listStripped.filter({$0 <= pivotValue})
// let greater = listStripped.filter({$0 > pivotValue})
let smaller = filter(listStripped, { $0 <= pivotValue })
let greater = filter(listStripped, { $0 > pivotValue })
return quicksort2(smaller) + Array(arrayLiteral: pivotValue) + quicksort2(greater)
}
//Benchmark
var d3 = NSDate()
quicksort2(list)
var d4 = NSDate()
var time2 = Float(d4.timeIntervalSinceDate(d3))
実行してみればわかりますがベンチマークの結果は激遅です。
これはSwiftのArrayが参照型ではなく値型なのが影響しているそうですが、改善方法がわからないのでどなたかご助言をいただけると嬉しいです。
参考
[Sigmapoint blog](http://blog.sigmapoint.pl/quicksort-the-swift-way/ "Quicksort the swift way")