代表的なソートアルゴリズムについて
情報系の勉強をしていると、なんやかんやソートアルゴリズムの問題にぶち当たる
概念は非常に理解しやすいものであるが、暗記力が弱い人にとってはなかなか苦戦するものである。
そこで、代表的なソートアルゴリズムの時間計算量についてまとめて記載し、いつでも見直せるようにこの記事を書く。
なお、この記事は一通りソートアルゴリズムについて理解した者が読むことを想定しているため、時間計算量についての説明などは記載しない。
1.バブルソート
ソートについて学ぶ上で最も基礎であろう交換ソートだ。
全ての要素nに関して、隣接する要素と比較し順序が逆であれば入れ替える。これをn-1回繰り返すことでソートを行う。なおこの繰り返しは、入れ替えが起こらなくなった時点で（それ以降は何度繰り返しても変化が起こらなくなるので）中断することができる。
1.1 動作例
初期データ: 8 4 3 7 6 5 2 1
結果が確定した部を太字でしめすと、
43765218（1回目の外側ループ終了時 交換回数:7）
34652178（2回目の外側ループ終了時 交換回数:5）
34521678（3回目の外側ループ終了時 交換回数:3）
34215678（4回目の外側ループ終了時 交換回数:2）
32145678（5回目の外側ループ終了時 交換回数:2）
21345678（6回目の外側ループ終了時 交換回数:2）
12345678（7回目の外側ループ終了時 交換回数:1）
交換回数の合計:7+5+3+2+2+2+1=22
1.2 時間計算量
最悪時間計算量 O(n²)
最良時間計算量 O(n)
平均時間計算量 O(n²)
データ構造としては配列を用いることで実装ができ、安定したソートアルゴリズムである。
2. クイックソート
クイックソートは一般的に最も高速と言われている交換ソートである。
適当な値（ピボット）を基準値として選択する
ピボット未満の要素を配列の先頭側に集め、ピボット未満の要素のみを含む区間とそれ以外に分割する
分割された区間に対し、再びピボットの選択と分割を行う
分割区間が整列済みなら再帰を打ち切り、ソート完了
2.1 動作例
確定した部分は太文字で表す。初期データ: 8 4 3 7 6 5 2 1
1 4 3 7 6 5 2 8 （ピボットを「7」とする）
左から７以上、右から７未満を探索し、入れ替える。
1 4 3 2 6 5 7 8 （7と2を入れ替える）
1 4 3 2 6 5 | 7 8 （探索終了したため、分割を行う）
1 2 3 4 6 5 | 7 8 （ピボットを「2」とする）
1 2 | 3 4 6 5 | 7 8 （探索終了したため、分割を行う）
1 | 2 | 3 4 6 5 | 7 8 （ピボットを「2」とし、探索した結果、右探索と左探索の双方が「2」であったので確定する）
1 | 2 | 3 4 5 6 | 7 8 （ピボットを「6」とする）
1 | 2 | 3 4 5 | 6 | 7 8 （ピボットを「3」とする）
1 | 2 | 3 | 4 5 | 6 | 7 8 （ピボットを「4」とする）
1 | 2 | 3 | 4 | 5 | 6 | 7 8 （ピボットを「8」とする）
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 （ソート完了）
2.2 時間計算量
最悪時間計算量 O(n²)
最良時間計算量 O(n log n)
平均時間計算量 O(n log n)
データ構造としては配列を用いることで実装ができ、安定していないソートアルゴリズムである。
3. 選択ソート
選択ソートは、片方から確定させていくソートアルゴリズムである。
1 番目の要素から最後尾の要素までで最も値の小さいものを探し、それを 1 番目の要素と交換する（1番目の要素までソート済みとなる）
以降同様に、未ソート部分の最小要素を探索し、未ソート部分の先頭要素と交換する
すべての要素がソート済みになったら処理を終了する
3.1 動作例
確定した部分は太文字で表す。初期データ: 8 4 3 7 6 5 2 1
1 4 3 7 6 5 2 8 （1回目のループ終了時）
1 2 3 7 6 5 4 8 （2回目のループ終了時）
1 2 3 7 6 5 4 8 （3回目のループ終了時）
1 2 3 4 6 5 7 8 （4回目のループ終了時）
1 2 3 4 5 6 7 8 （5回目のループ終了時）
この例では、一見して、この時点で既にソート完了したとわかる。しかしデータが多数の場合はそうはいかないし、アルゴリズムで「一見して」ソート完了か否か判断できない。アルゴリズム通りに最後まで処理する必要がある。
1 2 3 4 5 6 7 8 （6回目のループ終了時）
1 2 3 4 5 6 7 8 （7回目のループ終了時）
3.2 時間計算量
最悪時間計算量 O(n²)
最良時間計算量 O(n²)
平均時間計算量 O(n²)
データ構造としては配列を用いることで実装ができ、安定していないソートアルゴリズムである。
4. ヒープソート
ヒープソートは二分ヒープ木の概念を理解することが最も早い。
ヒープアルゴリズムについては、このサイトに記載があるが一応まとめておく。
アルゴリズムは、以下のように2つの段階から構成される。
未整列のリストから要素を取り出し、順にヒープに追加する。すべての要素を追加するまで繰り返し。
ルート（最大値または最小値)を取り出し、整列済みリストに追加する。すべての要素を取り出すまで繰り返し。
4.1 時間計算量
最悪時間計算量 O(n log n)
最良時間計算量 O(n)
平均時間計算量 O(n log n)
そもそも二分ヒープ木を作成するのに以下のような最悪計算量を示せる。
追加：O(log n)
削除：O(log n)
さらにデータの取り出しを行いソートされた配列作成の時間計算量は、O(n)で示すことができる。
よって最悪時間計算量がO(n log n)になるのは必然だろう。
データ構造としては配列・（二分ヒープ木）を用いることで実装ができ、安定していないソートアルゴリズムである。
5. 挿入ソート
挿入ソートは人間がトランプゲームをするとき、並び替える手法として最もメジャーなソートアルゴリズムである。
まず0番目と1番目の要素を比較し、順番が逆であれば入れ換える。次に、2番目の要素が1番目までの要素より小さい場合、正しい順に並ぶように「挿入」する（配列の場合、前の要素を後ろに一つずつずらす）。この操作で、2番目までのデータが整列済みとなる（ただし、さらにデータが挿入される可能性があるので確定ではない）。このあと、3番目以降の要素について、整列済みデータとの比較と適切な位置への挿入を繰り返す。
5.1 動作例
整列された部分（確定とは限らない）をアンダーライン、挿入する部分を太字で表す。
84376521（初期データ）
48376521（1回目のループ終了時）
34876521（2回目のループ終了時）
34786521（3回目のループ終了時）
34678521（4回目のループ終了時）
34567821（5回目のループ終了時）
23456781（6回目のループ終了時）
12345678（7回目のループ終了時。ソート完了）
5.2 時間計算量
最悪時間計算量 O(n²)
最良時間計算量 O(n)
平均時間計算量 O(n²)
データ構造としては配列を用いることで実装ができ、安定しているソートアルゴリズムである。
6.マージソート
マージソートは「分割統治法」の代表的なソートアルゴリズムである。言葉の通り、「分割」と「統治」の2つのステップに分かれている。
基本的な手順は以下の通りである。
データ列を分割する（通常、二等分する）
分割された各データ列で、含まれるデータが1個ならそれを返し、2個以上ならステップ1から3を再帰的に適用してマージソートする
二つのソートされたデータ列（1個であればそれ自身）をマージする
6.1 動作例
整列された部分（確定とは限らない）をアンダーライン、挿入する部分を太字で表す。
8 4 3 7 6 5 2 1（初期データ）
8 4 3 7 | 6 5 2 1（2つに分割する）
8 4 | 3 7 | 6 5 | 2 1（要素が2つになるまで分割する）
4 8 | 3 7 | 5 6 | 1 2（要素内でソートをする）
3 4 7 8 | 1 2 5 6（マージを行う）
1 2 3 4 5 6 7 8（マージを行う）
6.2 時間計算量
最悪時間計算量 O(n log n)
最良時間計算量 O(n log n)
平均時間計算量 O(n log n)
データ構造としては配列を用いることで実装ができ、安定しているソートアルゴリズムである。
7. ボゴソート
ボゴソートは非常に効率の悪いソートとして知られている。実装される例はほぼなくユーモラスソートと呼ばれている。
トランプを例に挙げてソート方法を説明する。
7.1 動作例
トランプ52枚の束を放り投げて、ばらばらにする。
1枚ずつ無作為にすべてを拾い集める。
ソートされているか確認する。もしソート済みでなければ、1から3までの手順を繰り返す。
カードの束をひたすらシャッフルし続けて順番に並ぶまで待つアルゴリズムと考えてもよい。
7.2 時間計算量
最悪時間計算量 O(∞)
最良時間計算量 O(n)
平均時間計算量 O(n×n!)
データ構造としては配列を用いることで実装ができ、安定していないソートアルゴリズムである。
まとめ
7つの代表的なアルゴリズムを挙げた。これらのアルゴリズムは様々なシステムの挙げた。
最後に表にしてまとめておく。
ここまで読んでくれた全ての人に、この記事が有意義なものとなることを願っている。
