【プログラミング初心者】Swift練習問題~クイックソート~回答例

#クイックソート
##回答例
```swift
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)
}
```
##解説
再帰関数で処理しています。

```swift
if list.count == 0 {
    return list
}
```
ここは終了条件です。
与えられた配列が空となった場合処理を終了します。
空配列の場合`if`に入るので`return []`としても同じです。

```swift
let pivot = list[0]
```
ピボットを定義します。
今回の場合、配列の先頭をピボットとしています。

```swift
var excludedPivotList = list
excludedPivotList.remove(at: 0)
```
ピボットを配列の要素から除外しています。
除外しないとピボットが大きいグループor小さいグループに入ってしまうため、比較の際はピボットを除外した配列に対してループ処理を行ないます。

```swift
var lagger: [Int] = []
var smaller: [Int] = []
```
大きいグループを`lagger`、小さいグループを`smaller`という新しい配列として定義します。
比較した値をそれぞれの配列振り分け追加していきます。

```swift
for item in excludedPivotList { 
    if item > pivot {
        lagger.append(item)
    } else {
        smaller.append(item)
    } 
}
```
比較するためにループを回します。
取り出した値とピボットを比較し大きければ`lagger`、小さければ`smaller`に値を格納します。

```swift
return quickSort(list: lagger) + [pivot] + quickSort(list: smaller)
```
配列を結合します。
`lagger`、`smaller`はまだ整列済みでないため再帰処理としてさらにソートを掛けています。

###処理時間の比較
実際バブルソートと比べてどれくらい早くなったか比較してみます。
以下を実行してください。かなり早くなっているのではないかと思います。
※バブルソートの実装は[こちら](https://qiita.com/euJcIKfcqwnzDui/items/306979a03fc813615720#%E5%9B%9E%E7%AD%94%E4%BE%8B)を使用しています。

```swift
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`の配列オブジェクトを毎回作っています。
これは再帰で階層下の処理を行っている間も上で生成したオブジェクトは残っており、かなりメモリを使用していまう実装となっています。
また、オブジェクトの作成自体も多少時間がかかる処理のため最大効率とは言えない実装となっています。

あくまで本投稿はアルゴリズムの練習という位置づけのため詳しくは言及しませんが、本来は最初に与えた配列オブジェクトをそのまま使っていき、その配列の中でインデックス指定で値を入れ替えていくのが良い実装と言えます。
その実装例は以下となります。
余裕があれば詳しく解析してみてください。

```swift
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))秒")
```
*参考：https://qiita.com/ymmtmdk/items/acfd1ae29ec389ed97ac*