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

ソート処理の続き

ソート処理では安定性があった方が望ましいです。ソートにおける安定性は前回、説明していますが政局の安定というような意味合いではなく、ソートキーの値が同じになったときの並びに関することです。

ひとつの例としてある組織の会員を年齢の若い順に整理する場合を考えます。会員は年度ごとに退会、新規会員を反映させて整理する場合、同一年齢のときは従来会員の後に、新規会員の順番を割り振った方が自然です。

安定性が保証されないクイックソートでもコードを追加したりデータに元の順番を追加すれば安定性が保たれます。安定性のないアルゴリズムにおいて安定性を保証するには、第1ソートキーの値が両者で等しいときに第2のソートキーを元の順番にしてソーティングするコードを追加します。

C言語では変数のビット長は32ビットで、倍長変数は64ビットです。第1ソートキーと第2ソートキーを合成して倍長変数にすれば、コードを追加することなく一般アルゴリズムで安定性のあるクイックソートにすることができます。以下に具体例を示します。構造体の定義と最後のサンプルデータに注目ください。

改良されたソートキー

// 構造体の定義
struct member{
    char *address;     // 住所
    char *name;        // 氏名
    union utag{
        ULONG seq[2];  // 元の順番
        ULONGLONG age; // 年齢
    }key;
};

// 2012-07-29,改良版

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

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

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

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

struct member data2011[]={//Sort-key 元の順 年齢
"山川市瑞穂町3-4-5", "佐藤一郎", 0, 32,
"山郷市水森町1-2-3", "斉藤花子", 1, 25,
"内海市戸板街9-8-7", "高橋次郎", 2, 47,
"外海市黒川町6-5-4", "鈴木三郎", 3, 19,
"河山市瑞穂町3-4-5", "後藤四郎", 4, 54,
"水郷市水森町1-2-3", "渡辺桃子", 5, 61,
"外海市黒川町3-703", "東山一郎", 2012072401,25,
"外海市黒川町3-704", "東山次郎", 2012072402,70,
"外海市黒川町3-705", "東山三郎", 2012072403,47,
"外海市黒川町3-706", "東山四郎", 2012072404,32,
"外海市黒川町3-707", "東山五郎", 2012072405,47,
"外海市黒川町3-708", "東山六郎", 2012072406,52,
"外海市黒川町3-718", "西山七郎", 2012072407,32
};