基本的なものから高速化されたものまで、様々なソートアルゴリズムの手法、計算量をわかりやすく解説して行きます。
挿入ソート
挿入ソートは、データを整列済みと未整列の2つにわけ、未整列の配列からデータを取り出して、整列済みの適切な部分の挿入することを繰り返すことでソートを行う手法です。
最悪計算量はO(n2)と遅いですが、整列化されている部分が多いほど計算量が減り、処理速度が向上します。
選択ソート
選択ソートは、データから最小値を探し、配列の先頭要素と入れ替えていくことを繰り返すことでソートを行う手法です。
最悪計算量がO(n2)と遅いため、基本的には他のソートアルゴリズムが使用されますが、配列が小さく選択ソートが高速に動作することが保証されている場合はこちらが使用されることもあります。
バブルソート
バブルソートは、データ列の隣合う要素を比較し交換を繰り返すことで整列を行う手法です。
単純で実装が容易なソート法ではあるのですが、挿入ソート、選択ソートと同様に最悪計算量がO(n2)と遅いので、他のソートアルゴリズムが使用されることが多いです。
また、基本交換法、隣接交換法と言われることもあります。
シェルソート
シェルソートは、配列の中である程度間隔が離れた要素の組ごとに挿入ソートを行い、間隔を小さくしながら、挿入ソートを繰り返すことで高速化する手法です。
挿入ソートの一般化とされるソートアルゴリズムとなっており、計算量はO(n1.25)～O(n1.5)と挿入ソートと比べ高速化が行われています。
挿入ソートは安定ソートですが、シェルソートは不安定になってしまうといったデメリットもあります。
ヒープソート
ヒープソートは、二分ヒープ木を用いて、最大値・最小値を取り出して整列を繰り返して整列を行う手法です。
※ヒープとは、半順序木と呼ばれ「親＞＝子」または「親＜＝子」といった性質をもちます。
計算量は、O(n log n)と速いですが、安定ソートではありません。
選択ソートの改良版のソートアルゴリズムになります。
クイックソート
クイックソートは、適当な基準を決めて、「基準値より小さい値」のグループと「基準値より大きい」のグループに分ける作業を繰り返して整列を行う手法です。
クイックソートのように、分割を繰り返して整列を行う手法のことを分割統治法と言います。
平均計算量は、O(n log n)と速いですが、最悪計算量はO(n2)と遅いためどんな場合にも速いソートアルゴリズムではありません。
マージソート
マージソートは、配列を2つに分轄しそれぞれを整列した後、2つをマージして整列を行う手法です。
既に整列してある複数個の配列をマージする際に、小さいものから並び変えれば新しい配列も整列されているという、ボトムアップの分割統治法によるソートアルゴリズムです。
平均計算量は、O(n log n)と速いソートアルゴリズムになります。
まとめ
表にまとめると下記の通りになります。
| 名称 | 計算量 | 安定性 |
| 挿入ソート | O(n2) | 〇 |
| 選択ソート | O(n2) | × |
| バブルソート | O(n2) | 〇 |
| シェルソート | O(n1.25)～O(n1.5) | × |
| ヒープソート | O(n log n) | × |
| クイックソート | O(n log n)～O(n2) | × |
| マージソート | O(n log n) | 〇 |
コメント