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

ソート

ソートとは

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

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

この記事は、ソートアルゴリズムを考える上で重要な概念である「安定性」、「内部ソート」と「外部ソート」について、そして基本的なソートアルゴリズムの簡単な説明と計算量の比較をすることを目的とします。

ソートの安定性(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が並びます。

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

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

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

内部ソートと外部ソート

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

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

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

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

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

アルゴリズム最善時間平均時間最悪時間領域安定内部
選択ソート\(\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)\)

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

ソート

Posted by cs-learner