qsort() 関数 〜配列の中身を、順番に並べ替えるには〜
☆ qsort() 関数とは？−何に使う関数なのか−
今、ここに12人の生徒がいるとします。
そして手元には、この12人の生徒のテストの点数データがあります。
| 太郎 | 次郎 | 三郎 | 四郎 | 五郎 | 六郎 | 七郎 | 八郎 | 九太郎 | 十子 | 十一郎 | 十二郎 |
| 50 | 30 | 90 | 44 | 13 | 46 | 82 | 43 | 70 | 74 | 20 | 62 |
先生は、この12人に順位を付けて、教室の掲示板に貼り出したいと考えています。
しかし、このままでは、順位表を作れません。
そんな時に、これらの点数を順番に並べ替えてくれるのが、qsort()
関数です。
☆ 具体的には
qsort() は quick sort
の略で、ソートとは数字や文字列を並べ替えることです。
このqsort関数は、１つの配列中にある数字や文字を、順番に並べ替えてくれる関数です。
例えば、
| int Tensu[] = { 50 , 30 , 90 , 44 , 13 , 46 , 82 , 42 , 70 , 74 , 20 , 62 }; |
となっているデータを、
| int Tensu[] = { 13 , 20 , 30 , 42 , 44 , 46 , 50 , 62 , 70 , 74 , 82 , 90 }; |
という風に並べ替えてくれます。
それどころか、
| int Tensu[] = { 90 , 82 , 74 , 70 , 62 , 50 , 46 , 44 , 42 , 30 , 20 , 13 }; |
という風に、降順に並べ替えることもできます。
もちろん、文字や小数、構造体の整列も可能です。
☆ qsort() 関数の使い方
さて、そんな便利なqsortですが、１つ欠点があります。
それは、使い方を覚えるのが、非常に難しいことです。
このqsort()
関数の定義は、こうなっています。
| void qsort ( void* base , size_t nmemb , size_t size, int(*compar)(const void *, const void *) ) |
ワケが分かりません。
いきなり void*
とか言われても初心者には何の事やら分かりませんし、一番右の
int(*compar)‥‥に至っては、
何の事やらさっぱりです。
しかし、そのまま使わずに、ほったらかしにするには非常に勿体ない関数です。
そこで、この意味不明な定義を意訳してみると、こういう意味になります。
| void qsort ( 並べ替えたい配列のアドレス , その配列のサイズ , sizeof(その配列の型) , int型の比較関数へのポインタ ) |
例えば、int型の配列 Tensu を並べ替えるには、こう記述します。
| qsort(Tensu , 12 , sizeof
(int) , MyComp );
日本語訳： 大きさが12の、int型配列Tensuを並べ替えなさい。 |
そして、もしも、大きさが100の配列 「 float Sincho[100] 」を並べ替えたいのであれば、
| qsort(Sincho , 100 , sizeof (float) , MyComp ); |
と記述すれば並べ替えてくれます。
☆ MyComp って何さ？
‥‥しかし、上記の文を、そのままコンパイラに通すと、エラーが出ます。
なぜなら、関数 MyComp
は、標準のライブラリ関数ではないからです。
というか、引数に関数を使うこと自体、馴染みの無い方も多いかもしれません。
そしてqsort関数が使いにくい理由は、ここにあります。
実は、qsort()関数を使うには、自分で比較関数を作らなくてはいけません。
どんな関数を作らなくちゃいけないのかと言うと、数字同士を比較する関数です。
ａとｂの２つの数を比較して、ａの方が大きければ正の数を返し、ｂの方が大きければ負の数を返す。
そんな関数を自作しなければ、qsort()関数は動いてくれないのです。
しかしそれは、逆に言えば、その関数を作るコツさえマスターすれば、どんな型のソートでも可能になるという事です。
とりあえず、ここでは long
型の数値を比較する関数を作ってみることにしましょう。
| int MyCmp(const void* a , const void* b) { long *x, *y; x = (long*) a; y = (long*) b; return x - y; } |
関数には必ず、const void*
型の引数を２つ用意する必要があります。
そして、上記は long 型の比較を行いたい場合の関数ですが、もしも double
型の比較を行いたい場合は、
以下のような関数を作ります。
| int MyCmp(const void* a , const void* b) { double *x, *y; x = (double*) a; y = (double*) b; return x - y; } |
そして、文字の比較を行いたい場合（例えば、ACGBDFE
となっているのを、ABCDEFG という風に並べ替える）には、
上の関数の赤字の部分を、char
に変えた関数を作って、qsort()
に使わせることもできます。
さらに、この関数を工夫すれば、こんな事もできます。
| struct Seiseki { char Name[10]; int Tensu; }; Seiseki Juni[12]; /* 構造体Juni[n]に、各生徒の名前と点数を代入する処理 （省略） */ qsort(Juni , 12 , sizeof(Seiseki ) , MyComp ); int MyCmp(const void* a , const void* b) { Seiseki *x, *y; x = (Seiseki*) a; y = (Seiseki*) b; return (x ->Tensu ) - (y -> Tensu); } |
また、上の例では、「１、２、４、９、12‥‥」という順番（昇順）に並べ替えますが、これを２文字変えるだけで、
逆の降順（12、９、４、２、１‥‥）に並べ替えることもできます。
| int MyCmp(const void* a , const void* b) { long *x, *y; x = (long*) a; y = (long*) b; return y - x; } |
また、こうすることで、ランダムに並べ替えることもできます。
| int MyCmp(const void* a , const void* b) { return (rand()%2) ? 1 : -1 ; } |
このように、qsort()
関数は、覚えるのは難しいですが、使いこなせば使いこなすほど便利に使える、
非常に奥の深い関数です。
（覚えにくいけど使えば使うほどクセになる‥‥なんかC言語みたい；）
☆ 補足
・関数MyCmpには、const void
型の引数を２つ用意する必要がありますが、qsort()文を使うときには、
MyCmpと入力するだけで十分です。引数は必要ありません。qsort()関数が、勝手に引数を当てはめてくれます。
・数字や文字をソートする方法は、このクイックソートの他にもバブルソートや挿入法など、色んな方法があります。
が、データの数が多いときには、基本的にこのクイックソートが、一番速いと言われています。
・しかし、クイックソートは「順序どおりに並んでいるデータ」に非常に弱いです。
たとえば、「１、２、３、４、５‥‥1000万、1000万１、1000万２‥‥」というデータの場合、滅茶苦茶遅くなります。
逆順の場合は、さらに遅くなります。
☆ このページの要約−結局、何が言いたいのか？−
・関数qsort()は、配列変数の中身を、指定したとおりに並べ替えてくれる関数である。
・関数qsort()を使うには、まず自分で関数を作る必要がある。
それは、以下のような関数である。
| int MyCmp(const void* a , const void* b) { long *x, *y; x = (long*) a; y = (long*) b; return x - y; } |
上記は、long型の配列を並べ替えたい場合の関数である。int型を並べ替えたい場合は赤字の部分をintに、
char型を並べ替えたい場合は、赤字の部分をcharに変えれば良い。
・以上のような自作関数を用意した上で、以下の文を打ち込めば、qsort()は正常に動いてくれる。
| qsort( Kingaku , 100 , sizeof (long) , MyComp );
日本語訳： 大きさが 100 の、long 型配列 Kingaku を並べ替えなさい。 |
・なお、MyCompの工夫次第では、逆順に並べ替えたり、構造体配列を並べ替えたりすることもできる。