rustでアルゴリズム実装３（バブル、マージソート）＋O-記法

[前回](http://qiita.com/tkyk0317/items/4618b1d6eb2bd86a3044)に引き続き、rustの練習を兼ねて、[アルゴリズムクイックリファレンス](https://www.amazon.co.jp/アルゴリズムクイックリファレンス-第2版-George-T-Heineman/dp/4873117852/ref=sr_1_1?ie=UTF8&qid=1502070074&sr=8-1&keywords=アルゴリズムクイック・リファレンス)を実装していきたいと思います。
今回は、バブルソートとマージソートを実装していきたいと思います。

## インストール
[こちら](http://qiita.com/tkyk0317/items/9b00893a838eb6a88de2)を参照して、rust環境を整えてください。

## 環境
- MacBook Pro (Sierra 10.12.6 Retina)
- 2.3GHz IntelCore i7
- Memory 16GB
- NVIDIA GeForce GT 750M 2048MB Intel Iris Pro 1536MB
- rustc v.1.19.0

## バブルソート

[wikipedia](https://ja.wikipedia.org/wiki/バブルソート)より。

```
バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。
最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。
安定な内部ソート。基本交換法、隣接交換法ともいう。（単に交換法と言う場合もある）
```

以下、実装になります。

```rust:bubble.rs
// バブルソート..
pub fn sort<T: Ord>(data: &mut Vec<T>) {
    let len = data.len();
    let mut end = len;
    while end > 0 {
        for i in 0..data.len() - 1 {
            // 隣同士の要素を比較＆入れ替え.
            if data[i] > data[i + 1] { data.swap(i, i+ 1); }
        }
        end -= 1;
    }
}
```

## マージソート

[wikipedia]()より。

```
マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。
大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。
n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分割と統合の実装にもよるが、一般に安定なソートを実装できる。
インプレースな（すなわち入力領域を出力にも使うので追加領域を必要としない）ソートも提案されているが、そうでない通常の場合は、O(n)の外部記憶を必要とする。
（ナイーブな）クイックソートと比べると、最悪計算量は少ない。ランダムなデータでは通常、クイックソートのほうが速い。
```

以下、実装になります。

```rust:merge.rs
use std::fmt::Debug;

// マージソート本体.
pub fn sort<T: Ord+Clone+Debug>(data: &mut Vec<T>) {
    let mut src = data.clone();
    let end = data.len();
    merge_sort(&mut src, data, 0, end);
}

// マージソート実処理部.
fn merge_sort<T: Ord+Clone+Debug>(work: &mut Vec<T>, result: &mut Vec<T>, start: usize, end: usize) {
    // 要素数が１つになればリターン.
    if end - start < 2 { return; }

    // 要素が２つしか存在しない場合、入れ替える.
    if end - start == 2 {
        if result[start + 1] < result[start] {
            result.swap(start, start + 1);
            return;
        }
    }

    // 領域を半分に分割し、其々をソート.
    let mid = (start + end) / 2;
    merge_sort(result, work, start, mid);
    merge_sort(result, work, mid, end);

    let mut idx = start;
    let mut left = start;
    let mut right = mid;
    while idx < end {
        // 右の要素のほうが大きい、もしくは左側に要素が無い場合、右側から取得.
        if left >= mid || (right < end && work[left] > work[right]) {
            result[idx] = work[right].clone();
            right += 1;
        }
        else {
            result[idx] = work[left].clone();
            left += 1;
        }
        idx += 1;
    }
}
```

## 処理速度

[前回](http://qiita.com/tkyk0317/items/4618b1d6eb2bd86a3044)までの結果に今回実装したバブルソート、マージソートの処理時間を追加しました（要素数10,000）。

| ソート種別 | 処理時間       |
|:---------- |:---------------|
| Vec::sort  | 0.000456419sec |
| 挿入       | 0.049269012sec |
| 選択       | 0.161756264sec |
| ヒープ     | 0.057409270sec |
| クイック   | 0.000540712sec |
| バブル     | 0.207203747sec |
| マージ     | 0.000770333sec |

また、要素数を増加させながら、各ソートアルゴリズムの処理時間を計測しました。
(5,000要素スタートで、5,000要素毎増加させ、100,000まで増加させた際の処理時間を計測）

![ソートアルゴリズム処理時間グラフ](https://cl.ly/312k3h0j1A0E/sort_algorithm.png)


高速に動作しているソートアルゴリズムが見えにくい（というか、全く見えない）ので、別グラフで表示します。

![ソートアルゴリズム処理時間グラフ（Vec::sort、qsort、クイックソート、マージソート)](https://cl.ly/383x3Y0I0p2P/sort_algorithm.png)

## まとめ
今まで実装した6種類のソートアルゴリズム（挿入、選択、ヒープ、クイック、バブル、マージ）に関して、まとめたいと思います。

| ソート種別    | 計算量         | メモリ使用量   | 安定性     |
|:--------------|:---------------|:---------------|:-----------|
|選択ソート     | $O(n^{2})$     | $O(1)$         | ☓[^1]      |
|挿入ソート     | $O(n^{2})$     | $O(1)$         | ◯         |
|バブルソート   | $O(n^{2})$     | $O(1)$         | ◯         |
|ヒープソート   | $O(n \log n)$   | $O(1)$         | ☓          |
|クイックソート | $O(n \log n)$   | $O(\log n)$     | ☓          |
|マージソート   | $O(n \log n)$   | $O(n)$[^2]     | ◯         |

### 計算量の評価（O-記法）

計算量は、$O(f(n))$として表現されます（[O-記法](https://ja.wikipedia.org/wiki/ランダウの記号))。
nを無限大にまで増加した場合（つまり、nが非常に大きくなった場合）、計算量がどのように変化するのかを示したものです。

代表的なものに関して、例を上げてみます。

| O-記法      | 概要                                           | 例                             |
|:-----------|:-----------------------------------------------|:------------------------------|
| $O(1)$     | 定数時間で処理が完了する。データ数に依存しない。          | 配列から１つのデータを取り出す       |
| $O(N)$     | データ数に比例。ループを一回だけ行っているものが該当。      | 線形探索(配列から１つのデータを探索）  |
| $O(N^{2})$ | データの自乗に比例。二重のループ処理を行っているものが該当。 | 挿入ソート、バブルソート             |
| $O(\log N)$  | データ数の対数に比例。処理を行う度に対象とするデータ数が減る。| バイナリサーチ                    |
| $O(N!)$    | データ数の階乗に比例。                              | 巡回セールスマン問題              |

[^1]: 安定ソートとしても実装可能
[^2]: In-Placeマージソートだと、$O(1)$で実装可能

## ソートの安定性とは？

「安定なソート」とは、キーが同じである要素が２つ以上存在するデータをソートした場合、ソート前後で順番が変化しないものを指します。
例えば、クイックソートやヒープソートでは、順番が変わる可能性があるので「不安定なソート」、挿入ソートやマージソートでは順番が変わらない為、「安定なソート」となります。

## 参考
- [ランダウの記号](https://ja.wikipedia.org/wiki/ランダウの記号)
- [計算量オーダーについて](http://qiita.com/asksaito/items/59e0d48408f1eab081b5)
- [Algorithm Visualizer](http://algo-visualizer.jasonpark.me/#path=backtracking/knight's_tour/basic)
    - アルゴリズムをVisual化するサービス。色々なアルゴリズムをVisual化できる。