ソートアルゴリズム まとめ

とある企業の面接対策で、ソートアルゴリズムについてどんなものか、自分の理解のためにまとめました。
残念ながら、その企業からは残念ながらオファーがもらえなかったのですが・・・
（その話は誰かの役に立ちそうなので、ほとぼりが冷めた頃にブログ化しようと思います。）

今回はソートについて、今後の備忘録でまとめておきます。
計算時間とか空間量は自信がないので、間違ってたらどなたか指摘いただけると嬉しいです。

0. 基礎知識

安定 / 不安定なソート：
比較した結果、同値である要素が、順序性を保つ場合を「安定」、保たない場合を「不安定」という。
例えば、a = [2, 1, 2] のような配列を考えると、ソート後は [1, 2, 2] になるが、これを s とおく。
安定ソートの場合、a[0] = s[1]、a[2] = s[2] といった形で、順序が保たれることが保証されるが、不安定なソートである場合、a[0] = s[2]、a[2] = s[1] と、同値なものがソートしたあとに入れ替わることがある。

内部 / 外部ソート：
ソートは、メモリの領域を必要とする。
要素 n の配列であれば、少なくとも O(n) のメモリ領域が必要だが、アルゴリズムによっては、追加のメモリ領域が必要なものもある。
(Wikipedia では auxiliary という形で追加の空間計算量が表記されている。)
この追加のメモリ領域が、たかだか O(log(n)) 程度しか必要としないようなソートを内部ソート、O(n) 以上の領域を必要とするソートを外部ソートという。
本記事では、この追加のメモリ領域を「空間計算量」として表記している。

1. バブルソート

配列の値で隣どおしの値の大小を比較し、整列していく。
1 ループごとに、右端に最大値が入っていく。

平均計算時間： O(n^2)
最悪計算時間： O(n^2)
空間計算量： O(1)
安定/内部ソートである。

例：

[5, 1, 4, 3, 6, 2] - 5 と 1 を比較して交換
[1, 5, 4, 3, 6, 2] - 5 と 4 を比較して交換
[1, 4, 5, 3, 6, 2] - 5 と 3 を比較して交換
[1, 4, 3, 5, 6, 2] - 5 と 6 を比較して何もしない
[1, 4, 3, 5, 6, 2] - 6 と 2 を比較して交換
[1, 4, 3, 5, 2, 6] - 6 が右端に来たので、[1, 4, 3, 5, 2] でもう一度ソート。これを繰り返していくと、ソートが完了する。

2. 選択ソート

配列の中から最小値を探し、左端に入れていく。

平均計算時間： O(n^2)
最悪計算時間： O(n^2)
空間計算量： O(1)
不安定/内部ソートである。

例：

[5, 1, 4, 3, 6, 2] - 5 と 1 を比較して、小さい値として 1 を記録
[5, 1, 4, 3, 6, 2] - 1 と 4 を比較して、小さい値として 1 を記録
・・・これを繰り返し、最小値が 1 と分かるので、左端に 1 を入れ、1 がいた場所には 5 を入れる。
[1, 5, 4, 3, 6, 2] - 1 が左端に来たので、[5, 4, 3, 6, 2] でもう一度最小値を取得し、ソートを行う。これを繰り返してソートを完了させる。

3. 挿入ソート

1 番目の要素と 2 番目の要素を比較して整列した後、3 番目以降の要素は、比較済みの要素のうち適切な位置に挿入していく方法。

平均計算時間： O(n^2)
最悪計算時間： O(n^2)
空間計算量： O(1)
安定/内部ソートである。

例：

[5, 1, 4, 3, 6, 2] - 1 番目の要素と 2 番目の要素を比較し、整列する。
[1, 5, 4, 3, 6, 2] - 3 番目の要素である 4 を、1 と 5 と比較し、5 より小さいので 5 の前に挿入する。
[1, 4, 5, 3, 6, 2] - 4 番目の要素である 3 を、1, 4 と比較し、4 より小さいので 4 の前に挿入する。
[1, 3, 4, 5, 6, 2] - 5 番目の要素である 6 を 1, 3, 4, 5 と比較し、どの要素よりも大きいので、位置は動かさない。
[1, 3, 4, 5, 6, 2] - 6 番目の要素である 2 を 1, 3 と比較し、3 より小さいので 3 の前に挿入する。
[1, 2, 3, 4, 5, 6] - ソート完了。

4. マージソート

まず要素を 1 つずつの配列に分割する。
隣合う配列の先頭どうしを比較し、小さい値を新規配列の末尾に順次入れていく。
これを繰り返すことでソートを完了させる。

平均計算時間： O(nlog(n))
最悪計算時間： O(nlog(n))
空間計算量： O(n)
安定/外部ソートである。

例：

[5, 1, 4, 3, 6, 2] - 要素を 1 つずつに分解する。
[5] [1] [4] [3] [6] [2] - 配列 [5] と配列 [1] を比較して、小さい方の値である 1 を新規の配列に入れ、そのあとに大きい方の値である 5 を入れる。
[1, 5] [4] [3] [6] [2] - 配列 [4] と配列 [3] を比較して、小さい方の値である 3 を新規の配列に入れ、そのあとに大きい方の値である 4 を入れる。
[1, 5] [3, 4] [6] [2] - 配列 [6] と配列 [2] を比較して、小さい方の値である 2 を新規の配列に入れ、そのあとに大きい方の値である 6 を入れる。
[1, 5] [3, 4] [2, 6] - 配列 [1, 5] と配列 [3, 4] の先頭どうし、1 と 3 を比較して、小さい値である 1 を新規の配列に入れる。
[1] [5] [3, 4] [2, 6] - 配列 [5] と配列 [3, 4] の先頭どうし、5 と 3 を比較して、小さい値である 3 を、1 を入れた配列の末尾に入れる。
[1, 3] [5] [4] [2, 6] - 配列 [5] と配列 [4] を比較して、小さい値である 4 を、1, 3 を入れた配列の末尾に入れる。
[1, 3, 4, 5] [2, 6] - 配列 [1, 3, 4, 5] と配列 [2, 6] の先頭どうしを比較して、小さい値である 1 を新規の配列に入れる。
[1] [3, 4, 5] [2, 6] - 配列 [3, 4, 5] と配列 [2, 6] の先頭どうしを比較して、小さい値である 2 を 1 を入れた配列に入れる。これを繰り返してソート完了。

5. クイックソート

ピボットを基準として、ピボットより小さいリストと大きいリストに分割する。
小さいリストと大きいリストそれぞれについて、再びピボットを選び、それぞれ小さいリスト・大きいリストに分割する。
これを要素数が 1 になるまで繰り返すことで、ソートを完了させる。

平均計算時間： O(nlog(n))
最悪計算時間： O(n^2)
空間計算量： O(log(n))
不安定/内部ソートである。

例：

[5, 1, 4, 3, 6, 2] - ピボットとして中央の値である 4 を選択する。
[5, 1, 4, 3, 6, 2] - 左端から 4 以上の値を走査し、5 を見つける。右端から 4 以下の値を走査し 2 を見つける。これらの位置を交換する。
[2, 1, 4, 3, 6, 5] - 左の続きの位置から値を走査し、4 以上の値である 4 と、右の続きの位置から値を走査し、4 以下である 3 があるので、位置を交換する。
[2, 1, 3, 4, 6, 5] - ピボットである 4 を基準に配列を分割する。
[2, 1, 3] [4] [6, 5] - [2, 1, 3] のピボットとして、中央の値である 1 を選択する。
[2, 1, 3] [4] [6, 5] - [2, 1, 3] について左から 1 以上の値を走査し、2 を見つける。右から 1 以下の値を走査し、1 を見つける。これらの位置を交換する。
[1, 2, 3] [4] [6, 5] - ピボットである 1 を基準に、[1, 2, 3] を分割する。
[1] [2, 3] [4] [6, 5] - [2, 3] のピボットとして、2 を選択するが、特に交換は不要なので 2 を基準に [2, 3] を分割する。
[1] [2] [3] [4] [6, 5] - [6, 5] のピボットとして、6 を選択する。左から 6 以上の値を走査し、6 を見つける。右から 6 以下の値を走査し、5 を見つける。これらの位置を交換する。
[1] [2] [3] [4] [5, 6] - ピボットである 6 を基準に、[5, 6] を分割する。
[1] [2] [3] [4] [5] [6] - これをマージしてソート完了。

6. シェルソート

挿入ソートを改良したもので、挿入ソートが「ほとんど整列されたデータに対しては高速である」という性質を利用している。

与えられたソート対象を、4 つ飛びや 8 つ飛びのリストに分割して、それぞれのリストをソートしたあと、より短い間隔に縮めて分割・ソートを繰りかえす。
これを繰り返し、最終的に 1 つずつ挿入ソートしてソートを完了させる。

平均計算時間： O(n(log(n)^2)
最悪計算時間： O(n^2)
空間計算量： O(1)
不安定/内部ソートである。

例：

[5, 1, 4, 3, 6, 2] - 間隔 2 (1 つ飛び) のリストに分割する。
[5, 1, 4, 3, 6, 2] - [5, 4, 6] と [1, 3, 2] で挿入ソートを行う。[5, 4, 6] について 5 と 4 をまず交換する。
[4, 1, 5, 3, 6, 2] - 6 はすでに適切な位置にあるので、[5, 4, 6] はソート完了。続いて [1, 3, 2] について 1 と 3 を整列しようとするが、すでに適切な位置にあるので何もしない。
[4, 1, 5, 3, 6, 2] - [1, 3, 2] について 2 を 3 の手前に挿入する。これで間隔 2 のソートは完了。
[4, 1, 5, 2, 6, 3] - 続いて、間隔 1 のリストとして挿入ソートを行ってソート完了。

7. 分布数え上げソート

ソート対象の中で、最小値から最大値までに対応したメモリ領域を用意する。
例えば、最小値が 0 で最大値が 9 なら、0 から 9 までの値に対応するよう 10 の領域を用意する。
次に、値を走査し、数に応じて、対応するメモリ領域に格納する数をインクリメントする。例えば、値が 3 であれば、Memory[3] に 1 を格納する。
全ての数についてインクリメントの処理が終わったら、メモリに格納された値を順番に見ていき、格納されている数だけ、メモリ領域が対応している数をアウトプットすればソート完了となる。例えば、Memory[0] = 1, Memory[1] = 2, Memory[2] = 1 なら、[0, 1, 1, 2] といった具合になる。

平均計算時間： O(n + k)
最悪計算時間： O(n + k)
空間計算量： O(k)
(ここで k は、ソート対象の最小値と最大値の幅を表す。)
安定/内部ソートである。

例：

[5, 1, 4, 3, 6, 2] - 最小値 が 1、最大値が 6 なので、6 つのメモリ領域を用意する。
[5, 1, 4, 3, 6, 2] - 値を走査し、対応するメモリ領域をインクリメントする。今回は 6 つすべてに 1 が入る。
[5, 1, 4, 3, 6, 2] - メモリに格納された値をもとに、数値をアウトプットする。
[1, 2, 3, 4, 5, 6] - ソート完了。

8. ヒープソート

2 分木：
各ノードが高々 2 個の子ノードを持つようなツリー構造。ノードが持つ値による順序性は特に考慮しない。

ヒープ：
子ノードが親ノードより常に大きいか等しい、もしくは子ノードが親ノードより常に小さいか等しい、という性質を満たす 2 分木のこと。

この 2 種類の概念を利用して、下記のようにソートする。

(1) ソート対象をそのまま 2 分木にする。
(2) 最大値が根ノードに来るようにヒープを構成する。
(3) 根ノードが最大値なので、これを新規のリストに入れる。
(4) 最も子要素のノードを、根となるノードに入れて、再びヒープを構成する。
(5) 根ノードが最大値となるので、これを (3) で利用したリストの左端に入れる。
(6) これを繰り返すことで、ソートされたリストができる。

平均計算時間： O(nlog(n))
最悪計算時間： O(nlog(n))
空間計算量： O(1)
(平均・最悪計算時間は nlog(n) だが、ヒープの構成などの処理により、クイックソートやマージソートより遅くなることが多い。)
不安定/内部ソートである。