C言語 構造体のクイックソート(配列要素の並び替え) - stdlib.h - [ qsort ]

2008.11.05 Wednesday | by LRESULT


イックソート(配列要素の並び替え)には、qsort()を使います。

今回は、応用編の構造体を対象としたクイックソートをやってみます。

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 ) : 比較関数
戻り値 なし



比較関数(comp)の戻り値(昇順の場合)
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 :正の値」という条件に当てはめています。

カテゴリ:C言語 stdlib.h | 21:17 | comments(0) | trackbacks(0) | -


コメントする











この記事のトラックバックURL

http://simd.jugem.jp/trackback/116

トラックバック