C言語 構造体のクイックソート(配列要素の並び替え) - stdlib.h - [ qsort ]
2008.11.05 Wednesday | by LRESULT
クイックソート(配列要素の並び替え)には、qsort()を使います。
今回は、応用編の構造体を対象としたクイックソートをやってみます。
※ qsort()の基本編は、こちら。
書式 | void qsort( void *base, size_t n, size_t size, int (*comp)( const void *c1, const void *c2 ) ) |
---|---|
機能 | クイックソート(配列要素の並び替え)を行う |
引数 | void *base : 並び替えを行う配列 size_t n : 配列要素の個数 size_t size : 配列要素のサイズ int (*comp)( const void *c1, const void *c2 ) : 比較関数 |
戻り値 | なし |
c1 < c2 | 負の値 |
---|---|
c1 == c2 | 0 |
c1 > c2 | 正の値 |
※ 比較関数の戻り値には、上記の規則があり、降順にするには不等号を逆にします。
時刻から生成した乱数を、構造体「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 :正の値」という条件に当てはめています。 |