主キーソート（キーの優先順位をつけてソート）

質問

時刻から生成した乱数を、構造体「TEST」のメンバ変数 a, b, c に代入し、
メンバb を基準にして、昇順にクイックソートしてみます。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct{
int a;
int b;
int c;
}TEST;

int comp( const void *c1, const void *c2 );

int main(void)
{
int i;
TEST base[10];

/* 乱数の生成 */
srand( (unsigned int)time( NULL ) );

for( i=0; i<10; i++ ){
base[i].a = rand() % 100; /* 0～99の乱数 */
base[i].b = rand() % 100;
base[i].c = rand() % 100;
printf( "%d¥t", base[i].a );
printf( "%d¥t", base[i].b );
printf( "%d¥t", base[i].c );
printf( "¥n" );
}

/* TEST構造体のbを基準にソート */
printf( "¥n--TEST構造体のbを基準にソート--¥n¥n" );
qsort( base, 10, sizeof(TEST), comp );

/* ソート後のデータを表示 */
for( i=0; i<10; i++ ){
printf( "%d¥t", base[i].a );
printf( "%d¥t", base[i].b );
printf( "%d¥t", base[i].c );
printf( "¥n" );
}

return 0;
}

/* 比較関数 */
int comp( const void *c1, const void *c2 )
{
TEST test1 = *(TEST *)c1;
TEST test2 = *(TEST *)c2;

int tmp1 = test1.b; /* b を基準とする */
int tmp2 = test2.b;

return tmp1 - tmp2;
}

ランダム結果
13 22 21
63 21 45
52 45 81
75 67 94
7 1 44
81 66 38
35 24 35
62 6 4
76 12 84
86 77 71

--TEST構造体のbを基準にソート--

7 1 44
62 6 4
76 12 84
63 21 45
13 22 21
35 24 35
52 45 81
81 66 38
75 67 94
86 77 71
と、このように表示されます。
下段の真ん中の列を見ると、メンバ変数 b で並び替えられている事が分かります。

比較関数comp内では、TEST構造体でキャストしてから、bを取り出しています。

また、戻り値に「tmp1 - tmp2」を使うことで、
「a < b ：負の値、a == b ：0、 a > b ：正の値」という条件に当てはめています。

とhttp://simd.jugem.jp/?eid=116で書かれていますが
これはb列を基準にしたソートであり、a列とc列の優先順位は書かれていません
キーの優先順位をb>a>cにするにはどうしたらよいでしょうか。

もっとたくさんキーあった時(a>b>c>d>e>f>g・・・)のようにキーの優先順位つけて昇順or降順にデータをソートしたいです。

よろしくお願いします

回答No.3

chie65535 · ベストアンサー

＞キーの優先順位をb>a>cにするにはどうしたらよいでしょうか。

int tmp1 = test1.b; /* b を基準とする */
int tmp2 = test2.b;

return tmp1 - tmp2;

を

int tmp1 = test1.b; /* b を基準とする */
int tmp2 = test2.b;

if (tmp1 != tmp1) return tmp1 - tmp2; /* bが不一致なら、その結果を返す */

tmp1 = test1.a; /* bが等しい場合のみ、次に a を基準とする */
tmp2 = test2.a;

if (tmp1 != tmp1) return tmp1 - tmp2; /* aが不一致なら、その結果を返す */

tmp1 = test1.c; /* bもaも等しい場合のみ、次に c を基準とする */
tmp2 = test2.c;

return tmp1 - tmp2;

に変えれば良いです。

d、e、f…と増やしたければ、同じように「優先するキーが不一致なら不一致と返し、一致した場合は次に優先するキーを比較」というのを、優先順位に合わせて繰り返しましょう。

お礼

なるほどです。なんかもやもやが取れてすっきりです。ありがとうございました。

回答No.2

maru_yoshi_

> これはb列を基準にしたソートであり、a列とc列の優先順位は書かれていません
確かにb列を基準にしたソートになっていますが、この例ではb列だけでソートできてしまうので、a列とc列の優先順位は無関係です。b列以外の優先順位が問題になるのはb列が同じ値である場合です。
このことを踏まえれば、

> キーの優先順位をb>a>cにするにはどうしたらよいでしょうか。
比較関数でb列が一致したとき、つまりtmp1 - tmp2の値が0のとき、a列の値を比べ、それが一致しているときにc列の値を比べればよいことがわかるはずです。
キーがたくさんある場合、優先度の高いものから比較して、大小の判定がつけば、判定結果を返し、大小判定がつかないとき（値が一致しているとき）に次の優先度について判定を行う。キーの大小判定がつくまでこの操作を繰り返せばいいです。

お礼

そういうことだったですね、納得です。ありがとうございました。

回答No.1

Tacosan

そ～いう比較関数を作ってください.

あ, ちなみにだけど, このプログラムで「クイックソート」するかどうかは分からんよ.