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

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

Contents

ソートとは

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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