クイックソート
回答例
func quickSort(list: [Int]) -> [Int] {
if list.count == 0 {
return list
}
let pivot = list[0]
var excludedPivotList = list
excludedPivotList.remove(at: 0)
var lagger: [Int] = []
var smaller: [Int] = []
for item in excludedPivotList {
if item > pivot {
lagger.append(item)
} else {
smaller.append(item)
}
}
return quickSort(list: lagger) + [pivot] + quickSort(list: smaller)
}
解説
再帰関数で処理しています。
if list.count == 0 {
return list
}
ここは終了条件です。
与えられた配列が空となった場合処理を終了します。
空配列の場合ifに入るのでreturn []としても同じです。
let pivot = list[0]
ピボットを定義します。
今回の場合、配列の先頭をピボットとしています。
var excludedPivotList = list
excludedPivotList.remove(at: 0)
ピボットを配列の要素から除外しています。
除外しないとピボットが大きいグループor小さいグループに入ってしまうため、比較の際はピボットを除外した配列に対してループ処理を行ないます。
var lagger: [Int] = []
var smaller: [Int] = []
大きいグループをlagger、小さいグループをsmallerという新しい配列として定義します。
比較した値をそれぞれの配列振り分け追加していきます。
for item in excludedPivotList {
if item > pivot {
lagger.append(item)
} else {
smaller.append(item)
}
}
比較するためにループを回します。
取り出した値とピボットを比較し大きければlagger、小さければsmallerに値を格納します。
return quickSort(list: lagger) + [pivot] + quickSort(list: smaller)
配列を結合します。
lagger、smallerはまだ整列済みでないため再帰処理としてさらにソートを掛けています。
処理時間の比較
実際バブルソートと比べてどれくらい早くなったか比較してみます。
以下を実行してください。かなり早くなっているのではないかと思います。
※バブルソートの実装はこちらを使用しています。
import Foundation
var list: [Int] = []
// ランダムな1000個の配列を作成
for _ in 1...1000 {
let randomNum = Int(arc4random()%1000)
list.append(randomNum)
}
// クイックソート実行時間測定
var before = Date()
var sortedList = quickSort(list: list)
var after = Date()
print("quick: \(after.timeIntervalSince(before))秒")
// バブルソート実行時間測定
before = Date()
sortedList = bubbleSort(list: list)
after = Date()
print("bubble: \(after.timeIntervalSince(before))秒")
quick: 2.307337999343872秒
bubble: 6.399366974830627秒
別解
今回の実装ですが、lagger、smallerの配列オブジェクトを毎回作っています。
これは再帰で階層下の処理を行っている間も上で生成したオブジェクトは残っており、かなりメモリを使用していまう実装となっています。
また、オブジェクトの作成自体も多少時間がかかる処理のため最大効率とは言えない実装となっています。
あくまで本投稿はアルゴリズムの練習という位置づけのため詳しくは言及しませんが、本来は最初に与えた配列オブジェクトをそのまま使っていき、その配列の中でインデックス指定で値を入れ替えていくのが良い実装と言えます。
その実装例は以下となります。
余裕があれば詳しく解析してみてください。
func quickSort2(list: inout [Int], from : Int, to: Int) {
if from < to {
var fromIndex = from
var toIndex = to
let pivot = list[fromIndex]
while true {
while list[fromIndex] < pivot {
fromIndex += 1
}
while pivot < list[toIndex] {
toIndex -= 1
}
if fromIndex >= toIndex {
break
}
let tmp = list[fromIndex]
list[fromIndex] = list[toIndex]
list[toIndex] = tmp
fromIndex += 1
toIndex -= 1
}
quickSort2(list: &list, from: from, to: fromIndex - 1)
quickSort2(list: &list, from: toIndex + 1, to: to)
}
}
var before = Date()
quickSort2(list: &list, from: 0, to: list.count - 1)
var after = Date()
print(list)
print("quick: \(after.timeIntervalSince(before))秒")