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

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



比較関数(comp)の戻り値(昇順)
c1 < c2 負の値
c1 == c2 0
c1 > c2 正の値

比較関数の戻り値には、上記の規則があり、降順にするには不等号を逆にします。





サンプルコード
時刻から生成した20個の乱数を、昇順(小さいものから順に)ソートしてみます。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

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

int main(void)
{
  int i;
  int base[20];

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

  for( i=0; i<20; i++ ){
    if( i % 4 == 0 ) printf( "¥n" );
    base[i] = rand() % 100;   /* 0〜99の乱数 */
    printf( "%d¥t", base[i] );
  }

  /* クイックソート */
  printf( "¥n¥n--クイックソート実行--¥n" );
  qsort( base, 20, sizeof(int), comp );

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

  return 0;
}

/* 比較関数 */
int comp( const void *c1, const void *c2 )
{
  int tmp1 = *(int *)c1;
  int tmp2 = *(int *)c2;

  if( tmp1 < tmp2 )  return -1;
  if( tmp1 == tmp2 ) return  0;
  if( tmp1 > tmp2 )  return  1;
}



結果
74      62      88      29
76      6       36      67
71      69      91      46
91      99      19      40
55      4       31      0

--クイックソート実行--

0       4       6       19
29      31      36      40
46      55      62      67
69      71      74      76
88      91      91      99
と、こんな感じで表示されます。

キッチリ昇順でソートされていますね。
ちょっと、面倒なところはありますが、自分でソートを作るよりかは簡単で高速です。
比較関数( comp() )内では、
引数が void*型の為、(int *)でキャストしてやる必要があります。

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


コメントする











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

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

トラックバック