ソートアルゴリズムの概要

2019年11月25日ソート入門,ソート

ソートとは

ソート(整列)とは、配列などのデータ構造について、ある順序関係に沿うように順番を入れ替えることです。簡単に言えば、小さいものから大きいものへと並ぶように整列させるようなものです。

ソートを行う場面は非常に多いため、実際には組み込みの関数やライブラリを用いてソートをするのがほとんどです。しかし、ソートのアルゴリズムはバラエティに富んでいて、アルゴリズムの学習には最適です。

まずは、基本的なソートアルゴリズムの一覧から、気になったものを見てみると良いでしょう。

後半に、ソートアルゴリズムを考える上で重要な概念である「安定性」、「内部ソート」と「外部ソート」についてを説明しますが、若干難しめなので必要になった段階で戻ってきて読んでも構いません。

基本的なソートアルゴリズムと計算量

以下が基本的なソートアルゴリズムの性能比較をした表です。

アルゴリズム最善時間平均時間最悪時間領域安定内部
選択ソート\(\Omega (n^2)\)\(\Theta (n^2)\)\(O (n^2)\)\(O (1)\)
バブルソート\(\Omega (n)\)\(\Theta (n^2)\)\(O (n^2)\)\(O (1)\)
挿入ソート\(\Omega (n)\)\(\Theta (n^2)\)\(O (n^2)\)\(O (1)\)
マージソート\(\Omega (nlogn)\)\(\Theta (nlogn)\)\(O (nlogn)\)\(O (n)\)
クイックソート\(\Omega (nlogn)\)\(\Theta (nlogn)\)\(O (nlogn)\)\(O (1)\)

※選択ソートはアルゴリズムを少し変更すると、不安定なソートから安定ソートに変化します。

細かい説明

ソートの安定性(Stability)とは

「安定性(Stability)」は表などをソートする際に、重要になる概念です。

順序的に同じ値を持つ要素が複数存在した時に、ソート後もその順序が保たれると「安定(stable)」といい、そうでない場合を「不安定(unstable)」といいます。

もう少しだけ厳密に書くと、\(<\) をソートに使用する順序関係、A をソート前の配列、B[i] を \(i\) 番目にあった要素のソート後のindexとした時に、任意のindexである \(i,j\) について

$$「(i<j) \land (A[i]=A[j])」 \Rightarrow 「B[i]<B[j]」$$

が成り立つ時、「安定」といいます。

具体例

例えば、以下のような表をソートする時を考えてみましょう。

番号名前年齢
0Ken17
1Risa17
2Takashi18
3Aoi18

この表を名前でアルファベット順になるようにソートすると以下のようになります。

番号名前年齢
3Aoi18
0Ken17
1Risa17
2Takashi18

ここで、年齢でソートするときが問題です。安定ソートでは以下のように、同じ年齢ならば名前は昇順に並んでくれます。つまり、Kenの次にRisaが来て、Aoiの次にTakashiが並びます。

番号名前年齢
0Ken(Risaより前)17
1Risa17
3Aoi(Takashiより前)18
2Takashi18

しかし、不安定なソートを使用すると、以下のように順番が入れ替わってしまう可能性があります。

番号名前年齢
1Risa17
0Ken(Risaより後)17
2Takashi18
3Aoi(Takashiより後)18

内部ソートと外部ソート

ソート時のメモリの消費量も、重要な考察対象です。配列の内部を使って処理を進めるか、配列の外部のメモリを使うかで分類されます。

配列の要素を入れ替えたりすることで処理をすすめる(In-placeな)ソートを内部ソートと言います。領域計算量は\(O(1)\)や\(O(logn)\)となります。

それに対して、ソートされる配列以外にデータを一時的に記憶し、\(O(n)\)以上の領域計算量が必要なものを外部ソートと言います。

ソート入門,ソート