[基礎]ソートアルゴリズム
2007年01月04日（木）18:45｜谷口
谷口です。
今回はプログラマの基本に立ち返って、ソートアルゴリズムについて書きます。
たいていの入門書で、必ずと言っていいほど登場するので、ご存知の方が多いとは思います。しかも、最近ではほとんどの言語で関数として実装されてますので、自分でコードを書くことはまずないかと思います。
そんなソートアルゴリズムですが、高速化されてきた実績もありますので、処理が遅いロジックに遭遇したときに、高速化のヒントがあるかもしれませんので、復習のつもりで読んでみて下さい。
ソートとは
ソートとは、データをある基準にしたがって並び換える処理のことを指します。 とりあえず、これまで考案されてきたソートアルゴリズムを少し挙げてみます。
- バブルソート（基本交換法，Bubble Sort）
- インサーションソート（基本挿入法, Insertion Sort）
- セレクションソート（基本選択法, Selection Sort）
- マージソート（Merge Sort）
- クイックソート’(Quick Sort)
- …etc
それぞれ昇順ソート、データ数nとして、順々に説明していきたいと思います。
また、javascriptで実装してみましたので、参考までにご覧ください。 javascriptにまだ慣れていないせいもあり、ソースはきれいではありません･･･。
各プルダウンメニューが見出しのソートに対応しております。 ソートされた結果だけでなく、交換or代入を行った回数と、ループの終了判定を含む比較演算の回数を出力します。各ソートは基本のものしか実装しておりませんので、下記で記述されている高速化の工夫は、今後暇を見つけて組んでみようかなと思ってます。
バブルソート
泡が浮き上がってくるかの如く並び換えられるため、この名が付けられたそうです。 簡単に手順を記述しますと、下記のようになります。
STEP0 データ確保、初期化（i=0）など STEP1 i番目の要素がi+1番目の要素より大きければ、i番目の要素とi+1番目の要素を交換。そうでなければ、そのままにする。 STEP2 i=i+1にしてi=n-2になるまでSTEP1を繰り返す。 STEP3 n=n-1，i=0にし、n=1なら終了、そうでなければSTEP1に戻る。
STEP3になるとき、n番目の要素には走査した中の最大値が入ります。つまり、大きい値ほど後方から順々に確定されていく感じです。 計算量は、O(n2) となります。 そのままの手順では、交換が全く起こらなくても一定数の比較演算が実行されてしまいますが、1 STEP3を工夫することで多少高速化できます。2
また、これを改良したシェーカーソートやコムソートといったアルゴリズムも考案されています。
インサーションソート
その名の通り、確定リストの中に未確定要素を入れていきます。同様に手順を示します。
STEP0 データ確保、初期化など STEP1 1番目の要素が2番目の要素より大きければ、1番目の要素と2番目の要素を交換。そうでなければ、そのままにする。また、この部分を確定リストとし、それ以外を未確定リストとする。 STEP2 未確定リストから、要素を一つ抜き出す（順番は何でも良い）。ここで抜き出した要素をkとする。 STEP3 kを確定リスト中の順序が変わらないように挿入する。 STEP4 未確定リストが空だったら終了、そうでなければSTEP2に戻る。
これはバブルソートより早いのですが、計算量の観点からすると同じくO(n2)となります。ただし、STEP3を工夫することで多少高速化できます。*3 また、データが配列の場合、確定リストに挿入する際に、要素をずらす処理が別途発生してしまいます。
セレクションソート
未確定リスト中の最小値を探索して、確定リストを増やしていきます。
STEP0 データ確保、初期化（データ全部を未確定リストとする）など STEP1 未確定リストから最小値を取り出し、確定リストの最後尾に追加する。 STEP2 未確定リストが空なら終了、そうでなければ、STEP1に戻る。
最小値を取り出す際に、更新が起こった場所を記憶しておくことで、多少高速化できます。*4
マージソート
データを分割していき、分割されたデータを大小比較しながらマージしていく方法で、再帰的に処理します。
STEP0 データ確保、初期化など STEP1 渡されたデータの要素が1つだったら、STEP2へ。 そうでなければ、さらに2等分してSTEP1へ。 STEP2 2等分したデータがそれぞれ返ってきたら、それらをマージする。
再帰処理のため、この書式ではわかりにくいですね･･･ということで、擬似コードを示します。
function mergeSort(data){ if(dataの要素数 > 1){ dataを2分割し、それぞれleft, rightとする; return mergeData(mergeSort(left), mergeSort(right)); } else { return data; } }
といった感じです。 また、mergeData関数では、次の処理が行われます。
STEP1 leftの先頭とrightの先頭を比較して、小さい方を抜き出す。 STEP2 抜き出した要素をリストの先頭から順に格納する。 STEP3 どちらかが空になるまで、STEP1，STEP2を繰り返し、残った方を抜き出したリストの後方にそのまま追加して、そのリストを返す。
マージソートは計算量の見積もりが少し難しいところもありますが*5、最悪の場合O(nlogn)となります。なおn>lognなので、これまでのソートの中では計算量は最小となります。
クイックソート
ソートに関してそれほど知らなくても、名前は聞いたことがある人は多いと思います。マージソートと同様に再帰的に処理されます。
STEP1 適当な要素を選び、ピボットとする。*6 STEP2 ピボットより小さい要素を前方に、大きい要素を後方にすべて移動。 STEP3 要素数が3以下でなければ、ピボットを境に2つに分割し、それぞれに対してSTEP1, STEP2を実行。
実装方法は様々です。というのも、ピボットの選定方法が決められていないためです。
最悪の場合の計算量はO(n2)となってしまいますが、実測値上は最速と言われているソートです。（平均計算量:O(nlogn)）
おわりに
ここで紹介したソート以外にも、ヒープソート、バケットソート、基数ソートなど知られているソートがまだまだあります。また、それぞれのソートアルゴリズムの改良なども研究されておりますので、まだまだ高速化される可能性があります。 ただし、計算量的には理論限界がO(nlogn)であることが証明されている*7ため、速度向上の研究は実測値がメインとなっています。
記事を執筆するにあたって、主に確認用としてwikipedia:ソートを活用させていただきました。また、javascriptで組んでみた感想ですが、可視化を試みたりもしてたので、けっこう苦労しました。ソートのロジック自体はそれほど難しいものではないので、得意な言語で組んでみると面白いかもしれません。
注
*1: 入力となる要素数に依存します。
*2: 最後に交換が発生した場所をnにセットするなど。
*3: 探索アルゴリズム。ソート済みのデータから探索するので、二分探索などが有効になります。（二分挿入法）
*4: 探索領域を狭められる。次の探索では、一つ前に更新が起こった場所と、最小値が得られた場所以降を探索する。
*5: 各要素が比較される回数で考えると、わかりやすいと思います。
*6: ピボットの選び方で実行時間が変化します。
*7: wikipedia:ソート
