日別アーカイブ: 2012-07-25

ソート処理

ソートとは多くのデータをある規則にしたがって並び替えることです。コンピュータ処理では基本中の基本処理です。多数の手法が確立され、

①マージソート、②クイックソート、③シェルソート、④ヒープソート、⑤バブルソート、⑥選択ソート

などが有名です。規則では小さい順に並べることが多いようです。データは複数項目から成っていることが一般的で、たとえば住所、氏名、年齢のように3つのアイテムによって構成され、年齢順に並べるとき年齢項目をソートキーと言います。

年齢が同じになることはよくあることでこの場合、元の順序を保証するか順序不定の2ケースに分かれます。ソートでは元の順序を保証することを安定性があると言います。

安定性を保つことがソート手法ですぐれているとは一概に決めつけられませんが、順序が保障される方が良い場合が多いようです。基本アルゴリズムで保証されなくても処理を追加すれば改善することが可能です。 安定性は保証されませんが処理時間で最高位に立つと言われるクイックソートのCサンプルコードを紹介します。

<<< クイックソート関数 >>>

//
// name:sort function
// method:quick sort
//
// 配列要素i番目とj番目の値を入れ替える
void swap(int *i, int *j){ // 両者の値を交換する
int t = *i; // ワークエリアに退避
*i = *j; // 上書きする
*j = t; // 退避したものを設定
}

// 2012-07-29,改良版
void QuickSort(int data[], int l, int r){// このソート法では同じ値の順序は不定になる
// 探索配列要素 左端の配列要素 右端の配列要素
// ピボットとはクイックソートにおいて、ソートする際の基準とするデータのこと
int mid; // 中間値
int i, j;

if(l==r) return;
i = l;
j = r;
mid = data[(l+r)/2]; // ピボットの決定
for(;;){
while( data[i] < mid ) i++; // 左からピボット以上を探索
while( mid < data[j] ) j--; // 右からピボット以下を探索
if( i >= j ) break; // 探索地点がぶつかったら終了
swap(&data[i], &data[j]);// お互い発見した値をいれかえる
i++;
j--;
}

if ( l < i-1 ) QuickSort(data, l, i-1); // 再帰呼び出しで左半分ソート
if ( j+1 < r ) QuickSort(data, j+1, r); // 再帰呼び出しで右半分ソート
}

コンピュータの処理時間

コンピュータの処理時間は年々向上し、2足歩行ロボットなどは処理時間の高速化がその実現に貢献していると言えます。

一世を風靡したBASICインタープリタはパソコンを身近な存在にしましたが処理時間に物足りなさがありました。

複雑な計算を含む場合、1分を超すこともあり、あらかじめ計算してディスクにその結果を記憶しておき、求められたときディスクを検索して計算結果を引き出すシステム設計をしたことがありました。

たいへんなのは仕様変更やバグが発見されたときには、ディスクへの記憶のため、再び数時間を必要としたことでした。数年も経つとハードウェアとソフトウェアの進歩で高速処理が可能となり、求められたときに即、計算し結果を通知するように改められたことはいうまでもありません。

似たようなケースとして、かつて工学書の末尾に対数表や三角関数表が付録として添付されていましたが、今では電卓やパソコンにて容易に関数値を求められるようになったので、付録の作り方が大きく変化しました。科学の進歩が経済活動に変動を与える一例です。