LastUpdate : 07/02/01
基本的なソートアルゴリズムについての書いています。
私自身の知識の確認のため、作ってみました。処理速度のグラフなんかも書いていますが、それは私のパソコン（ペンティアムⅣ１．９Ｇｈｚ、メモリが５１２ＭＢ、ＯＳがWindowsXPＳＰ２です）での計測結果です。色々後ろで走っていたりもするので、正確な計測環境とはいえません＾＾；
以下の項目には、使用したソースコードから抜粋したものを乗っけています（アルゴリズムの記述部分）。
全体としてのソースコード（時間計測とかも含めたソース）は、以下から見れます。
計測に使用したソースコード（csvファイルに結果を出力する機能もオマケではいってたりしますｗ）
八つのアルゴリズムの処理時間をまとめたグラフと表が以下からみれます。
遅いソート（その１）と早いソート（その２）と、二つに分けました（時間のスケールが違いすぎるため）。新しいウインドウで開きます。
全体の処理時間の比較のグラフその１（バブルソート・挿入法・交換法・シェーカーソート
全体の処理時間の比較のグラフその２（クイックソート・シェルソート・マージソート・ヒープソート
☆ 処理時間の計測方法について
たとえばまず、５０００個の配列を、ソートルーチンにソートさせ、処理時間を計測します。
次に、配列のサイズを二倍にして（１００００個）ソートルーチンにソートさせ処理時間を計測させます。
・・・という繰り返しをやっています。このソート対象となる数値の入った配列についてですが、値はすべてランダムな値です。
また、例で書いたとおり、５０００個から１００００個などに、増加する際、１００００個の要素は、前回やった５０００個の要素に新たに５０００個の要素が加わっただけの配列です。
従来からある５０００個分はソートされていない状態に戻してあります。
平均計算時間がＯ（ｎ2）で、安定ソートです。
比較回数は「 n(n-1)/2 」です。
交換回数は「 約n2/2 」です（しかし、並び順によって異なる）。
このアルゴリズムの派生として、シェーカーソートやコムソートが有ります。
以下が今回使用したバブルソートのソースです。
最初から最後までの走査で一度も交換が行なわれない場合はソート完了とみなし、処理を終了させている処理もはいっています。
void bubble_sort(int *arr,int lim)
{
int flag;
int tmp;
int i,c;
for( i=0 ; i < lim ; i++ )
{
flag = 1;
for( c=0 ; c < lim-1-i ; c++ )
{
if( arr[ c ] > arr[ c+1 ] )
{
tmp = arr[c];
arr[c] = arr[c+1];
arr[c+1] = tmp;
flag = 0;
}
}
//ソート完了と見なせるため、終了。
if( flag )break;
}
}
|
配列の先頭からデータを走査し、最大値を探索する。このとき、[0]と[1]を比較したら次に[1]と[2]、次に[2]と[3]・・・と比較していく。この比較の際、添え字の少ないほうのデータのほうが大きかったら、比較したデータ同士で、入れ替える。
これを配列の最後まで繰り返すと、配列内の最大値が配列の最後に来ることになる。そして、次の処理では、配列のサイズを一つ減少したこととして再び処理を繰り返す。この繰り返しで、配列の要素が１個になるまで繰り返す。
すると、ソートがいつの間に完了しているというソート方法。
処理速度についての図：
平均計算時間がＯ（ｎ2）で、安定ソートです。
比較回数は「 n(n-1)/2以下 」です。
交換回数は「 約n2/2以下 」です。
以下が、今回使用した挿入法のソースです。
基本的に、挿入法はループが三つ必要ですが、以下のようにすると二つで済みます。実験で使用したソースには、ループが三つの方もコメントアウトされて入っています。
void insertion_sort(int *arr,int lim)
{
//ループを二つにした挿入法
int tmp;
int i,c;
for( i=1 ; i<lim ; i++ )
{
tmp = arr[ i ];
for( c=i ;; c-- )
{
if( arr[ c-1 ] < tmp || c == 0 )break;
arr[ c ] = arr[ c-1 ];
}
arr[ c ] = tmp;
}
}
|
挿入法は、まず、配列の[0]の部分を、ソート済み配列とみなします。そして[1]のデータをピックアップし、ソート済み配列（現在は[0]だけの部分を指す）の中に挿入するとしたらどこになるかなぁ・・・・と探索し、適当な場所（データを挿入しても、ソート済み配列とみなせる状態になるような場所。）するのが、挿入法ですです。
配列上での処理ならば、データを挿入するには、挿入する場所のデータを右側にずらさなければなりません。そのため、データをピックアップしたところと、挿入場所との間でデータを右側にずらす処理が必要になります。ピックアップした部分（[j]とする）というのは、すでに、退避させているので、ピックアップした場所の左側のデータ（[j-1]）をそのまま([j]へ)移動させてくることができます。そして、その左側のデータ([j-2])も、移動先（[j-1]）のデータはすでに右側([j])に移動させているので、データを移動させて・・・という処理が繰り返されます。
そして、ずらす処理が終わったならば、晴れてデータを挿入できる・・・というわけです。このとき、当然ですが、ソート済みである配列の部分の要素は一つ増えて、ソート済みではない配列の部分は一つ減ります。
そして、また、ソート済みではない配列の部分からデータをピックアップして・・・という繰り返しです。
ソート済みである配列に対してこの処理を行なうと、データの移動がまったく起こりません。そのため、ほとんどソート済みの状態の配列へのソート処理は非常に早いです。
処理速度についての図：
平均計算時間がＯ（ｎ2）で、安定ソートではありません。
比較回数は「 n(n-1)/2 」です。
交換回数は「 n-1以下 」です。
今回使用したソースコードです。
void selection_sort(int *arr,int lim)
{
int flag;
int point;
int i,c;
for( i=0 ; i<lim-1 ; i++ )
{
flag = 0;
point = i;
for( c=i+1 ; c<lim ; c++ )
{
if( arr[ point ] > arr[ c ] )
{
point = c;
flag = 1;
}
}
if( flag )
{
int tmp = arr[ i ];
arr[ i ]= arr[ point ];
arr[ point ] = tmp;
}
}
}
|
まず、i=0とします。そして、[i]から配列の最後までの区間から最小値を探索します。そして、最小値が発見されたら、最小値と[i]の値を交換します。そしてiの値をインクリメントし再び同じ処理を繰り返します。
そして、iの値をインクリメントしたとき、配列の要素の個数-1と同じになったら、処理を終了します（最後の要素は最大値となっているため）。
処理速度についての図：
最大の計算時間がＯ（ｎ2）で、安定ソートです。
以下が今回使用したシェーカーソートのソースです。
バブルソートを改良したアルゴリズムです。から、配列の最初バブルソートの１フェーズ分の処理を行なったら、次に配列の後ろから最初に向かって同じく、バブルソートの１フェーズを行ないます。
ある地点から終点まで交換が行なわれていないならば、その値を参考にし、次のフェースでは、その区間をスキップできたりします。
こう聞くと速そうなのですが、なんだか、そういうわけでもなかった・・・。ソースが間違ってるのかしら・・・？
ほとんどソート済みの配列に対しては、高速に処理できます。
void shaker_sort(int *arr,int lim)
{
int tmp;
int last_swap;
int head_last_swap_pos = lim-1; //head側で最後に交換が行なわれた場所。
int tail_last_swap_pos = 0; //tail側で最後に交換が行なわれた場所。
int i;
while( 1 )
{
last_swap = tail_last_swap_pos;
//head側
for( i=tail_last_swap_pos ; i<head_last_swap_pos ; i++ ) { if( arr[ i ] > arr[ i+1 ] )
{
tmp = arr[ i ];
arr[ i ] = arr[ i+1 ];
arr[ i+1 ] = tmp;
last_swap = i;
}
}
head_last_swap_pos = last_swap;
if( head_last_swap_pos == tail_last_swap_pos )break;
//tail側.
for( i=head_last_swap_pos; i>tail_last_swap_pos ; i-- )
{
if( arr[ i-1 ] > arr[ i ] )
{
tmp = arr[ i-1 ];
arr[ i-1 ] = arr[ i ];
arr[ i ] = tmp;
last_swap = i;
}
}
tail_last_swap_pos = last_swap;
if( head_last_swap_pos == tail_last_swap_pos )break;
}
}
|
処理速度についての図：
平均計算時間がＯ（ｎ Ｌｏｇ ｎ）で、安定ソートではありません。また、最大計算時間がＯ（ｎ2）です。
一般的に、最も高速なソートだと考えられているらしいです。これが考え出されたのって１９６０年ごろなんだそうで・・・＾＾；
今回使用したソースコードです。
再帰を使用していますので、ものすごい大きいデータをソートするときはスタックが溢れます。再帰を使わない方法もあるのですが、それだとスッキリとソースを書けないので＾＾；
//----------------------------------------------------------
//クイックソートの処理を行なう
static void quick_sort_sub(int *arr,int begin,int end)
{
if( begin >= end )return;
int tmp;
int left = begin;
int right = end;
int pivot = arr[ (left+right)/2+1 ];
while( 1 )
{
//左側から基準値より大きい値を探索。
while( arr[ left ] < pivot )left++;
//右側から基準値未満の値を探索。
while( arr[ right ] > pivot )right--;
if( left >= right )break;
tmp = arr[ left ];
arr[ left ] = arr[ right ];
arr[ right ] = tmp;
left++;
right--;
}
quick_sort_sub(arr,begin,left-1);
quick_sort_sub(arr,left,end);
}
//----------------------------------------------------------
//クイックソート（外部から呼び出される関数。
void quick_sort(int *arr,int lim)
{
quick_sort_sub(arr,0,lim-1);
}
|
クイックソートではpivotの値をどうするかが、一番重要です。
今回作りましたソースでは、単純に、配列の範囲の真ん中のデータの一つ右側をpivotとしていますが、いろいろとやりかたはあります。ちなみに、この＋１をやらないと、処理が終了しませんｗ
あと、これは紙に書いてトレースをしてみると面白い（？）です。
処理速度についての図：
平均計算時間がＯ（ｎ1.25）で、安定ソートではありません。
挿入法を改良したアルゴリズムです。
挿入法は、ほとんどソートされたデータをソートする際には、高速にソートができるので、これを生かし、あらかじめ、ある間隔ごとにデータをソートして、最終的に挿入法を行なう、という処理を行ないます。
この「ある間隔」がソートの処理速度を左右します。
わたしにはよくわからんのですが、とりあえず、以下のソースのように、ある値に３倍して１を足す、という処理をデータの要素数を超えるまで繰り返した値にすると、計算速度がＯ（ｎ1.25）になるらしいｗ
void shell_sort(int *arr,int lim)
{
int tmp;
int i,c,j,k;
int interval;
for( interval=1;interval<lim;interval=interval*3+1 );
for( i=interval ; i>0 ; i/=3 )
{
for( j=i ; j<lim ; j++ )
{
tmp = arr[ j ];
k = j - i;
for( c=j ; k>=0 && arr[ k ] > tmp ; c-=i,k-=i )
{
arr[ c ] = arr[ k ];
}
arr[ c ] = tmp;
}
}
}
|
まず、間隔（interval）を決め（これをgapとする）、[gap]と[gap*2]と[gap*3]と・・・・とgap*xがデータの範囲を超えるまでの間のデータを挿入法でソートします。
次に、gapをインクリメントし、再びおんなじことをします。
で、gapの値がデータの範囲外になったら、次にintervalを３で割り、これをgapに代入し、再び最初と同じことをします。
そして、intervalが１になると（３で割っていくと必ず１になるように、初期値を設定している）、挿入法とやっていることが同じになります。
挿入法はほぼソート済みの配列に対しての処理は高速ですので、高速に処理可能です。
だから、シェルソートは早い処理が可能です。一見、処理が増えているので遅いように思えるのですが・・・＾＾；
処理速度についての図：
平均計算時間がＯ（ｎ Ｌｏｇ ｎ）で、安定ソートです。内部ソートではない点が特徴です（メモリが有る程度必要になる）。
マージソートのソースです。
再帰を用いて書いています。また、とても特徴的なのが、シーケンシャルなデータアクセスです（最初から最後に向かって順番にアクセスされる）。
そもそも、外部記憶のデータ（テープとか）をソートするためのアルゴリズムらしいです。
ソートの処理でmemcpy関数を使っているところがあります。これはソートされた部分を元のデータへ戻している処理を行なっています。アルゴリズムの処理としては反則っぽいかも＾＾；
そして、tmpという変数は、外部に必要な一時記憶領域です。これがないとマージソートはできません（なので、ほかのソートと比較するとメモリを食う。しかし、メモリでなくても記憶できるものならなんでもいいです）。
//----------------------------------------------------------
//マージソートの処理を行なう。
static void marge_sort_sub(int *arr,int count,int *tmp)
{
if( count < 2 )return;
marge_sort_sub(arr,count/2,tmp);
marge_sort_sub(arr+count/2,count - count/2,tmp);
int i = 0;
int *tub1 = arr;
int *tub2 = arr+count/2;
int tub1_index = 0;
int tub2_index = 0;
int tub1_count = count/2;
int tub2_count = count - tub1_count;
while( tub1_index<tub1_count && tub2_index<tub2_count )
{
if( tub1[ tub1_index ] > tub2[ tub2_index ] )
tmp[ i++ ] = tub2[ tub2_index++ ];
else
tmp[ i++ ] = tub1[ tub1_index++ ];
}
if( tub1_index >= tub1_count )
while( tub2_index<tub2_count )tmp[ i++ ] = tub2[ tub2_index++ ];
else
while( tub1_index<tub1_count )tmp[ i++ ] = tub1[ tub1_index++ ];
//ソート済みのデータを元のデータへ上書きする。
memcpy(arr,tmp,count*sizeof(int));
}
//----------------------------------------------------------
//マージソート（外部から呼び出される関数。
void marge_sort(int *arr,int lim)
{
int *tmp = new int[ lim ];
if( !tmp )return;
marge_sort_sub(arr,lim,tmp);
delete []tmp;
}
|
マージソートは、まず、ソート対象のデータを二つに分割します。そして、自分自身を呼び出します。データの範囲が２個になるまで、呼び続けます。
そして、二個になったのならば、この二つのデータマージします（マージソートでいうマージは、両者の値をソートして一つの列にする、という意味）。そして、呼び出し元に戻ります。
呼び出し元に戻ると、呼び出し元でのデータ範囲は４つです。このデータをマージします。
このマージを行なう際、たとえば片っ方の要素が１，２、もう片っ方の要素が３，４となっている場合、マージ処理で、外部記憶に、１と最初書き込まれ、次に２と書き込まれます。
片っ方のデータはもうなくなっているので、次に、いきなりもう片っ方のデータをすべてくっつけて、１，２，３，４にすることができます。なぜなら、両方とも、一番初めにあるデータが最小値であるためです。そのため、ソートされたようになってしまっています。
そして、その処理が終了すると、このソースでは、ソート済みの箇所のデータを元のデータに上書きしています。これでこの範囲では、ソート済みになっています（一番初めの値が最小値）。
で、再び、呼び出し元にもどると・・・・・・・・と、マージ処理が繰り返されます。
処理速度についての図：
現在、予測と実験結果が一致しないので、原因を悩み中ｔｔ
平均計算時間がＯ（ｎ Ｌｏｇ ｎ）で、安定ソートではありません。
また、ソートを行なう際、データをヒープ構造に直さなければなりません。
今回作成したヒープソートのソースです。
あらかじめデータを、ヒープ構造に変換し、それからソートを行なわなくてはなりません。
ヒープソートはデータの並び順によって計算時間の変化があんまり無いという特徴もあります。
ヒープソートのアルゴリズムは、データへのアクセスがランダムアクセスです。また、並列処理に向かないアルゴリズムなんだそうです。
//----------------------------------------------------------
//ダウンヒープ([ pos ]にあるデータを正しい位置に配置する)
static void down_heap(int *arr,int pos,int count)
{
/*
//再帰版（再帰にすると遅い様です。
if( pos >= count/2 )return;
int tmp;
int k=0;
if( arr[ pos ] < arr[ pos*2+1 ] )
{
k = pos*2+1;
if( pos*2+2 < count )
if( arr[ pos*2+1 ] < arr[ pos*2+2 ] )k = pos*2+2;
}
else
{
if( pos*2+2 < count )
if( arr[ pos ] < arr[ pos*2+2 ] )k = pos*2+2;
}
if( k )
{
tmp = arr[ pos ];
arr[ pos ] = arr[ k ];
arr[ k ] = tmp;
down_heap(arr,k,count);
}
*/
if( count < 2 )return;
int tmp = arr[ pos ];
int i = pos;
int k;
while( i < count/2 )
{
k = 0;
if( tmp < arr[ i*2+1 ] )
{
k = i*2+1;
if( i*2+2 < count )
if( arr[ i*2+1 ] < arr[ i*2+2 ] )k = i*2+2;
}
else
{
if( i*2+2 < count )
if( tmp < arr[ i*2+2 ] )k = i*2+2;
}
if( k )
arr[ i ] = arr[ k ];
else
break;
i = k; //次の場所へ。
}
arr[ i ] = tmp;
}
//----------------------------------------------------------
//ヒープの形に並び替える。
static void create_heap(int *arr,int count)
{
int i;
for( i=count/2-1 ; i>=0 ; i-- )down_heap(arr,i,count);
}
//----------------------------------------------------------
//ヒープソート（外部から呼び出される関数。
void heap_sort(int *arr,int lim)
{
//ヒープを作成。
create_heap(arr,lim);
//昇順に並べる。
int tmp;
int j = lim-1;
while( j > 0 )
{
tmp = arr[ 0 ];
arr[ 0 ] = arr[ j ];
arr[ j ] = tmp;
down_heap(arr,0,j);
j--;
}
}
|
ヒープ構造とは、まず、以下のような位置関係とします。
[0]
[1] [2]
[3] [4] [5] [6]
・・・・
と一つのデータを頂点に子が二つあり、その子にも子が二つあり・・・という完全二分木の状態で、親の値が左の子と右の子の値より、大きい、という条件がヒープの成立条件です。
そして[番号]と書きましたのは、配列をヒープに見立てたときの、各要素の添え字です。添え字が0から始まる場合、必ず、親の添え字がiならば、左の子供の添え字はi*2+1、右の子供の添え字はi*2+2となります。
そして、子を持つデータの中で最も最後にある親の添え字を求めるには、cを配列のデータ数とするとc/2-1で求められます。
ヒープを作成した後は、[0]のデータと[配列の要素の数-1]のデータとを交換します。そして配列の要素の数をディクリメントします。
そして、[0]のデータをdown_heapします。[0]の子供[1]と[2]とを比較し、子の値が大きかった場合、その子供と値を交換し、そして、次に、その交換した場所の子の右の子、左の子と値を比較し・・・と同じことを繰り返し、葉にたどり着く、もしくは、交換が必要なくなるまで処理を繰り返します。
そしてまた[0]のデータと[配列の要素の数-1]のデータを交換し、配列のようその数をディクリメントします・・・と最初の処理の繰り返しを行ないます。
そして、配列の要素の数が１になったなら終了です。
処理速度についての図：
※ なんだか、思ったように速度がでてません。なので、現在、原因を考え中ですｔｔ
ヒープの平均計算時間はＯ（ｎ Ｌｏｇ ｎ）です。
create_heapの負荷が高いのかとおもったら、そうでもない様子でした・・・（16000000件のデータを、ヒープを作りソートするのと、すでにヒープになっているものをソートするのでは、前者では39047ミリ秒、後者で38250ミリ秒でしたので、あまり大きな差では無いみたいです。）。