ソートとは多くのデータをある規則にしたがって並び替えることです。コンピュータ処理では基本中の基本処理です。多数の手法が確立され、
①マージソート、②クイックソート、③シェルソート、④ヒープソート、⑤バブルソート、⑥選択ソート
などが有名です。規則では小さい順に並べることが多いようです。データは複数項目から成っていることが一般的で、たとえば住所、氏名、年齢のように3つのアイテムによって構成され、年齢順に並べるとき年齢項目をソートキーと言います。
年齢が同じになることはよくあることでこの場合、元の順序を保証するか順序不定の２ケースに分かれます。ソートでは元の順序を保証することを安定性があると言います。
安定性を保つことがソート手法ですぐれているとは一概に決めつけられませんが、順序が保障される方が良い場合が多いようです。基本アルゴリズムで保証されなくても処理を追加すれば改善することが可能です。 安定性は保証されませんが処理時間で最高位に立つと言われるクイックソートの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); // 再帰呼び出しで右半分ソート
}