アルゴリズムの代表的な分類の一つ、ソートアルゴリズム。
これは、データを昇順、あるいは降順に並び替えるための考え方だ。
本ブログでは、基本的なソートアルゴリズムについて解説をしてきた。
今回は、その全体像をまとめていこう。
それぞれの考え方、特徴をしっかり把握しておこう！
ソートアルゴリズムの全体像
まずは、ソートアルゴリズムをさらに分類し、含まれるものを列挙してみよう。
- 単純なソートアルゴリズム
- バブルソート
- 選択ソート
- 挿入ソート
- 高速なソートアルゴリズム
- クイックソート
- マージソート
- ヒープソート
- 要素同士を比較しないソートアルゴリズム
- ビンソート
- 分布数え上げソート
- 基数ソート
- その他のソートアルゴリズム
- シェルソート
- ボゴソート
上三つのカテゴリは、それぞれに3種類ずつのソートが存在する。
その他は、本ブログで紹介しているものは二つだ。
というわけで、計11個のアルゴリズムがある。
なお、実際にはこの11個以外にも存在する。
そこだけ覚えておいて欲しい。
ここから先は、各分類の特徴と、具体的なアルゴリズムについては大雑把な解説だけを行う。
詳細については、それぞれ解説した記事へのリンクを置いておくので、そこから参照してほしい。
単純なソートアルゴリズム
まずはこれ。
「単純な」とついている通り、どれも考え方が非常に単純で分かりやすい。
ただ、どれも計算量が\(O(n^2)\)で、わざわざこれらを使うメリットは薄い。
とはいえ、考え方を学ぶにはもってこいなので、是非勉強してみてほしい。
バブルソート
二つの隣接したデータを比較し、逆順だったら入れ替える、ということを繰り返すソートだ。
小さい要素が後ろから泡のように浮き上がってくることから、バブルソートという名がつけられている。
選択ソート
整列済みでない範囲から最小の要素を選択し、それを整列済みの部分の一番後ろと入れ替えるという考え方。
単純なソートアルゴリズム内で唯一安定でないソートなので、そこも注意しておこう。
挿入ソート
整列済みでない範囲内で先頭のデータを、整列済みの範囲の適した場所へずらしていくソートだ。
選択ソートと混同しやすいため、そこに気を付けて欲しい。
高速なソートアルゴリズム
二つ目のカテゴリだ。
これは計算量が\(O(n \log(n))\)という速さでソートを行うことができる。
その代わり、考え方が複雑になってくる。
また、前提知識として以下が必要なので、先に確認しておこう。
- アルゴリズム
- 再帰
- 分割統治法
- データ構造
- ヒープ
これらについても解説記事があるので、以下に貼っておく。
心配な方は、先にこちらから勉強しておこう。
クイックソート
あるデータを選び、それより大きいデータ、小さいデータに分割する、という操作を繰り返すことでソートを行う考え方だ。
考え方は複雑だが、非常に高速だ。
個人的な感覚だが、恐らく今回紹介している11個中最強だと思う。
データ構造による得意・不得意もあるが、常に候補の一つとして挙がってくるだろう。
マージソート
クイックソートと対をなすようなもの。
こちらはデータをとりあえず分割していき、くっつける時に小さい順にくっつける。
クイックソートと同じくらいややこしいので、しっかりデータの動きを見ていこう。
なお、このソートは連結リストで行うときに効力を発揮する。
ヒープソート
これは、他の二つとはちょっとタイプが異なる。
データ構造のヒープをそのまま使う考え方だ。
詳しくは記事を見て欲しいが、ヒープは特定の要素が必ず一番小さくなる。
それを取り出し、残りでまたヒープを作り、を繰り返すことでソートする。
面白いのは、これらを一つの配列だけで全て再現できてしまうこと。
前提知識の記事も併せて、しっかり理解してほしい。
要素同士を比較しないソートアルゴリズム
これまでは、どうしても要素同士を比較しなければいけなかった。
しかし、そのままだとどう頑張っても計算量は\(O(n log(n))\)までにしかならないことが証明されている。
じゃあどうするかというと、比較しなければいい。
というわけで、このカテゴリだ。
これらは、計算量\(O(n)\)という速さでソートを行うことができる。
しかし、条件がなかなかに厳しく、最低限どれも整数しか並び替えられない。
しかも、その整数が取る範囲も分からないといけなかったり、重複したデータがあったら無理なソートもある。
正直、計算量も劇的に速くなるかと言われるとそうでもない。
これらを使うのは、ちょっと特殊な状況になってくるだろう。
ビンソート
どの数字がデータに含まれているかのフラグを立てておき、小さい順にフラグが立っているものを並べるというソートだ。
このフラグを入れておく箱のことをbinと言うのでビンソート。
条件は、上に書いた三つ全てが必要となる。
なお、データのとりうる範囲があまりに大きいと効率が下がってしまうので注意だ。
分布数え上げソート
その名の通り、データの分布を見て、そこから位置を判断して並び替えるソートだ。
こちらの条件は、整数であることとデータの範囲が分かっていることの二つ。
重複はOKになり、さらに安定だ。
ビンソートと同じく、データのとり得る範囲は可能な限り狭い方がいい。
基数ソート
1の位から順番に安定なソートを繰り返していくというソートだ。
この1桁内のソートには、分布数え上げソートを使用する。
これにより、計算量\(O(n)\)を実現しているのだ。
その他のソートアルゴリズム
ここからは、上までのカテゴリに分類されないものを紹介する。
計算量も異なるので、それぞれで見ていこう。
シェルソート
これは挿入ソートの改良版だ。
計算量は大体\(O(n^{1.25})\)から\(O(n^{1.5})\)くらい。
そのまま挿入ソートをするよりはこちらを使おう。
ボゴソート
ネタだ。
ランダムに並び替え、それが揃っていればOKというもの。
実用的でないことは明白だろう。
なお、わずかデータ量10でもちょっと時間がかかる。
もうちょっとデータが増えれば、手で並び替えた方が速いというレベルの代物だ。
計算量は\(O(n \times n!)\)。
おわりに
今回は、これまで解説してきたソートアルゴリズム11個をまとめた。
どれも得意・苦手があったり、条件があったりするので、状況によってどれがベストかは変わってくる。
そこもしっかりと把握し、適切なソートを行うようにしていこう。
コメント