はじめに
アルゴリズム入門①計算量とソートの基本で計算量と基本的なソートに関してまとめたので、この記事では効率がよく、実用的なソートアルゴリズムに関してまとめます。
実用的なソートとは
アルゴリズム入門①計算量とソートの基本で紹介したソートアルゴリズムは$O(n^2)$で、効率が悪く、実用的ではありませんでした。
再帰・分割統治法などのテクニックを用いた、より高速で実用的なアルゴリズムを紹介します。
この記事で紹介するのは
- 常に$ O(n\log n) $の高速なアルゴリズム → マージソート
- 条件付きで$ O(n\log n)$で動くソートアルゴリズム → クイックソート
になります。
マージソート
以下のような手順でソートを行います。
- 配列を2つに分割する。
- 分割したそれぞれの配列をマージソートする。
- 二つのソートされた配列をマージする。
入力データを保持する配列以外に一時的なメモリ領域が必要になるという特徴を持ちます。
計算量が必ず$ O(n\log n)$になるという特徴がある。
クイックソート
以下のような手順でソートを行います。
- データの要素から任意の数を選ぶ(pivot)
- pivotより小さい数を配列left, pivotより大きい数を配列rightに入れる
- それぞれの配列に対して、再びクイックソートを行う。
- 要素数が1以下の領域ができた場合、その領域を確定とする。
- ソートされた配列left, pivot, ソートされた配列rightを結合する。
不安定なソート。
また入力値とpivotの選び方によっては、$O(n^2)$になるケースがある。
注意: 領域の左端の値が領域内で最小かつ、同じ値が他の位置にない場合、ピボットとしてその値を選ぶと無限ループとなってしまいます。
まとめ
| ソート名 | 最良 | 最悪 | 安定 |
|---|---|---|---|
| マージソート | $ O(n\log n)$ | $ O(n\log n)$ | ○ |
| クイックソート | $ O(n\log n)$ | $O(n^2)$ | × |
- クイックソートはピボットの選び方によっては$O(n^2)$になる。
- マージソートは必ず$ O(n\log n)$になる。