ソートアルゴリズム 計算量・特徴一覧
| 名称 | 最悪計算時間 \(O\) | 安定性 |
|---|---|---|
| 挿入ソート | \(O(n^2)\) | 安定 |
| バブルソート | \(O(n^2)\) | 安定 |
| 選択ソート | \(O(n^2)\) | 安定ではない |
| シェルソート | \(O(n^2)\) | 安定ではない |
| マージソート | \(O(nlog(n))\) | 安定 |
| クイックソート | \(O(n^2)\) | 安定ではない |
| ヒープソート | \(O(nlog(n))\) | 安定ではない |
アルゴリズム入門書はこの一冊で十分！
挿入ソート、バブルソート、選択ソート
この３つのソートは、「ソート済みの部分と未ソート部分に分ける」という共通方針がある。
部分的に分けた後、どのように未ソート部分をソートしていくのかがそれぞれ異なる。
>>【図解】挿入ソート：アルゴリズム【C言語のサンプルコート付き】
>>【図解】選択ソート：アルゴリズム【C言語のサンプルコード付き】
>>【図解】バブルソート：アルゴリズム【C言語のサンプルコード付き】
シェルソート
シェルソートは、一定の間隔\(n\)だけ離れた要素からなる集合に対して、挿入ソートを繰り返し行うアルゴリズムである。
\(n\)は、最初は大きい値から始め、挿入ソートを繰り返すごとに小さくしていく。
シェルソートの最悪計算時間は\(O(n^2)\) であるが、最初からある程度整列されたデータに対して高速に動作するという特徴がある。
マージソート
マージソートは、配列を\(n\)等分することを繰り返し、小さなブロック単位でソートした後、それらを全てマージ（統合）することで全体をソートするアルゴリズムである。
一般的には二等分していくことが多い。
配列を小さなブロックに分ける際に、元の配列以外の配列を使用するため、外部のメモリ領域を必要とするという難点がある。
クイックソート
クイックソートは、マージソートと同様に、ブロック単位でソートしていくアルゴリズムである。
マージソートが外部メモリを必要としたのに対し、クイックソートは1つの配列内で完結するため、外部のメモリ領域を必要としない。
クイックソートでは、ブロックの分割方法にパーティションを用いることで、内部ソートを実現している。
パーティション：配列内の、ある基準値よりも小さい値を左に、大きい値を右に移動することで配列を整えるアルゴリズム。一般的に、基準値は配列の端の数字に設定する。
また、クイックソートの最悪計算時間は\(O(n^2)\) であるが、パーティションにおいてバランスよく半分ずつに分割することができれば、\(O(nlog(n))\)となり、高速にソートを行うことができる。
ヒープソート
ヒープソートは、ヒープ構造を利用したアルゴリズムである。
ヒープ構造：普通の配列を二分木として扱うためのデータ構造。
実際のヒープ構造は、以下のようになっている。
通常の配列を最大（最小）ヒープへと整形することで、先頭ノードに最小値 or 最大値が来るため、その値を取って、残りを再び最大（最小）ヒープへと修正する、という動作を繰り返すことで全体をソートする。