5
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

Swiftでクイックソート

Last updated at Posted at 2015-07-19

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")

5
5
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
5
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?