【C言語】qsort関数の使い方

qsort関数の使い方の解説ページアイキャッチ

このページでは、C言語の標準関数である qsort 関数の使い方について解説します。

qsort 関数とは

まず、この qsort 関数がどのような関数であるのかについて解説します。

MEMO

配列をベースに解説しますが、malloc 関数などで確保したメモリ上のデータでも同様のことを行うことが可能です

qsort 関数は配列をソートする関数

qsort は、引数で指定した配列の各データをソートする関数です(並び替えする関数)。

qsort関数の動作を示す図

ソートを行う際に用いられるアルゴリズムは「クイックソート」です。qsortq を quick と考えると関数名が覚えやすいと思います。

クイックソートは名前の通り、ソート速度が高速である点が特徴です。クイックソートがどのようなアルゴリズムであるかは下記ページで解説していますので、詳しく知りたい方は是非下記ページを読んでみてください。

クイックソート解説ページのアイキャッチクイックソートを図を使って分かりやすく解説(C言語サンプルプログラム付き)

上のページを読んで見ていただければ分かると思いますが、クイックソートを行うためにはそれなりに実装は必要ですし、実装するためにはクイックソートがどんなものであるかを理解しておかなければなりません。

ですが、qsort 関数を利用すれば、わざわざクイックソートを自身でプログラミングしなくても、関数を呼び出すだけでクイックソートによるソートを実現することができます。

さらに、この qsort 関数では、どんな型の配列であってもソート可能であるという特徴を持ちます。

整数の配列をソートすることもできますし、文字列の配列をソートすることもできます。さらには、あなたが作成した構造体の配列でもソートすることができてしまいます。

qsort関数で文字列の配列をソートする様子を示す図

さらに、qsort 関数では、配列の各データを昇順および降順のどちらでもソート可能です。

qsort関数により昇順ソートと降順ソート両方を実行できることを示す図

スポンサーリンク

比較関数を自作する必要あり

ここまでの解説だけ読むと、この qsort 関数はかなり便利な関数に思えますね!

実際便利なのですが、便利である代わりに、ソート時に実行される “比較を行う関数(以降では比較関数と呼びます)” を作成し、その関数のアドレスを qsort 関数に渡してやる必要があります。ちょっとここがややこしいです。

要はソートとは、各データの大小関係を比較しながら、データ全体(配列全体)が昇順 or 降順に並ぶようにデータの並び替えを行う処理です。

ですが、その大小関係の比較自体は qsort 関数の中では行われません。なので、qsort 関数の利用者がその比較を行う関数を作成し、その関数のアドレスを qsort に渡してやる必要があります。

qsort関数実行時に比較関数のアドレスを渡す様子を示す図

そうすることで、比較を行う必要がある際に qsort 関数からその比較関数が実行され、その関数の結果に基づいてソートが行われるようになります。

比較関数を作成する必要があるのでちょっと手間はかかりますが、自分で好きなように比較関数を作成することができるため、上記のようにさまざまなソートを行うことが可能になっています。

基本的な qsort 関数の利用例

例えば下記では、int 型の配列 array の各データを昇順にソートする場合の qsort 関数の利用例になります(比較関数は compare)。

基本的なqsort関数の利用例
#include <stdio.h>
#include <stdlib.h>

/* 比較関数 */
int compare(const void *p_data1, const void *p_data2) {
    int ret;
    const int *p_int1 = p_data1;
    const int *p_int2 = p_data2;

    printf("%d と %d の比較\n", *p_int1, *p_int2);

    if (*p_int1 < *p_int2) {
        ret = -1;
    } else if (*p_int1 > *p_int2) {
        ret = 1;
    } else {
        ret = 0;
    }

    return ret;

}


int main(void) {

    int i;

    int array[10] = {
        8, 1, 9, 6, 7, 3, 5, 0, 2, 4
    };
    

    /* qsort関数の実行 */
    qsort(&array[0], 10, sizeof(array[0]), compare);
    
    for (i = 0; i < 10; i++) {
        printf("%d, ", array[i]);
    }
    printf("\n");

    return 0;
}

実行すると下記のように表示され、最後の1行から配列 array のデータが昇順にソートされていることが確認できると思います。

8 と 3 の比較
3 と 4 の比較
8 と 4 の比較
〜略〜
9 と 8 の比較
7 と 8 の比較
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 

また、他の行の出力から比較関数 compare が何回も実行されていることと、配列 array のデータ(のアドレス)が比較関数 compare の引数として渡されていることが確認できると思います(”8 と 3 の比較” といった比較時の情報を表示しているのは compare 関数)。

compare 関数は main 関数からは実行しておらず、前述の通り qsort 関数から実行されています。こんな感じで qsort 関数を実行すると、比較関数を実行してデータの比較を行い、その比較結果に応じてソートが行われます。

大体 qsort 関数の動作や比較関数との関係性は理解してもらえたのではないかと思いますので、ここからは個別に下記について解説していきたいと思います。

  • qsort 関数の使い方
  • 比較関数の作り方

qsort 関数の使い方

それでは qsort 関数の使い方(実行の仕方)について解説していきます。

スポンサーリンク

qsort 関数の定義

まず qsort の関数定義を確認してみましょう!qsort の関数定義は下記のようになります。

qsort関数
#include <stdlib.h>

void qsort(void *elems, size_t num_elem, size_t size_elem, int (* compar)(const void *, const void *));

まず qsortstdlib.h で宣言されていますので、qsort を使用する際には stdlib.hinclude する必要があります。

また、戻り値の型は void ですので、要は戻り値は “なし” です。

qsort 関数の引数

さらに、qsort 関数の各引数には下記を指定します。

  • 第1引数 elems:ソートを開始するデータのアドレス
  • 第2引数 num_elem:ソート対象のデータの数
  • 第3引数 size_elem:ソート対象の各データのサイズ(バイト)
  • 第4引数 compare:比較関数のアドレス

上記の引数に対し、qsort 関数では、アドレス elems から num_elem 個分のデータ(各データのサイズは size_elem)をソート対象として、ソートが実行されます。ソートに必要な比較は compare の指す関数により行われます。

qsort関数における各引数の意味合いを示す図

第1引数の型は void * で難しそうに感じるかもしれませんが、要はどんな型のアドレスを指定してもオーケーということです。一番よく指定するのは配列の先頭アドレスで、int 型の配列や構造体の配列等の先頭アドレスを指定することが可能です。

第4引数に関しては、関数のアドレスを指定するところが難しそうですが、C言語では単に関数名を記述することで、その関数のアドレスを取得することが可能です。

ですので、きちんと比較関数さえ作成していれば、後はその関数名を第4引数に指定すれば良いだけです(比較関数の作り方については、後述の比較関数の作り方で解説します。

qsort 関数の基本的な使い方

例えば、下記のような配列の全体をソートしたい場合について考えてみましょう。

ソートする対象の配列array
int array[100];

この場合、配列名は array、配列のデータ数は 100、配列の型は int なので、qsort 関数を下記のように実行することになります(比較関数の名前は compare としています)。

配列arrayに対するソートの実行
qsort(array, 100, sizeof(int), compare);

上記のように qsort 関数を実行すると、array[0]array[99] のデータがソートされた状態になります(比較関数 compare比較関数の作り方で説明した内容に基づいて作成していれば)。

また、下記のように qsort 関数を実行したとしても同じ結果を得ることができます。

配列arrayに対するソートの実行2
qsort(&array[0], 100, sizeof(array[0]),  compare);

スポンサーリンク

qsort 関数による配列の特定の範囲のみのソート

また、少し特殊な使い方になるかもしれませんが、配列全体ではなく配列の途中のデータのみをソートしたいような場合は、その範囲が特定できる形で qsort 関数を実行する必要があります。

例えば前述の配列 arrayarray[30]array[69]40 個のデータのみをソートしたいような場合は、下記のように qsort 関数を実行する必要があります。

配列arrayに対するソートの実行3
qsort(&array[30], 40, sizeof(int), compare);

要は、”ソートを開始するデータのアドレス” が &array[30] なので、これを第1引数に指定し、”ソートを行うデータの数” が 40 なので、これを第2引数に指定しています。

こんな感じで、特に第1引数と第2引数の指定を工夫することで、ソートを行う対象の範囲を変更することが可能です。

qsort 関数による構造体の配列のソート

また、前述の通り、qsort 関数ではどんな型のデータであってもソートすることが可能です。例えば下記のように構造体の配列に対して qsort 関数を実行することも可能です(比較関数 compare の定義は省略しています)。

構造体の配列に対するqsortの実行
#include <stdlib.h>

#define NUM_PEOPLE 10

typedef struct _PERSON {
    int age;
    int weight;
    int height;
    char name[256];
} PERSON;

int main(void) {

    PERSON people[NUM_PEOPLE];

    /* 配列の初期化 */

    qsort(people, NUM_PEOPLE, sizeof(PERSON), compare);

    return 0;
}

基本は前述の int の配列をソートする時と同じですが、第3引数で指定する “各データのサイズ” が異なるのでこの点だけは注意しましょう。

qsort 関数の使い方の解説は以上になります。

で、ここまでの解説を聞いて下記のような疑問を抱いた方もおられるのではないでしょうか?

  • 昇順ソートと降順ソートはどうやって指定するの?
  • 構造体の場合、どのメンバに対してソートされるの?

これらは引数で指定するのではなく、第4引数で指定するアドレスの “比較関数” によって決まります。つまり、比較関数の作り方によって昇順ソート or 降順ソートのどちらでソートを行うかや、構造体のどのメンバでソートするのかが決まります。

ということで、次は比較関数の作り方について解説していきたいと思います。

比較関数の作り方

それでは、比較関数の作り方について解説していきたいと思います。

まずは比較関数の役割を簡単におさらいしておきます。

前述の通り、比較関数は qsort 関数から実行される関数です。

この qsort 関数から実行される際、比較関数には2つのデータの格納されたアドレスが引数として渡されます。これらのデータはソート対象のデータのうちの2つになります。

比較関数の役割は、その2つのデータの大小関係を比較し、その結果に応じた値を返却することです。

qsort 関数は、その返却された値に応じてソート処理を進めますので、比較関数が正しく大小関係に応じた値を返却しないと、ソート結果も正しくなりません。

では、このような役割を持つ比較関数をどうやって作成していけば良いのかについて解説していきます。

スポンサーリンク

比較関数の引数の型と戻り値の型を指定する

まずは作成する比較関数の “引数の型” と “戻り値の型” について解説していきます。

みなさんも関数を作成する時には引数の型と戻り値の型を決めますよね?

当然ですが、今回作成する比較関数においても引数の型と戻り値の型を決める必要があります。ではどのように決めれば良いでしょうか?

この答えは、qsort の関数定義を見れば分かります。再掲ですが、下記が qsort の関数定義になります。

qsort関数
#include <stdlib.h>

void qsort(void *elems, size_t num_elem, size_t size_elem, int (* compar)(const void *, const void *));

注目していただきたいのが第4引数です。前述の通り、qsort 関数実行時には、この第4引数に比較関数のアドレスを指定します。

この第4引数の型、すごく難しそうに見えますが、要は下記のような比較関数のアドレスを引数に指定して欲しいことを示しています。

  • 戻り値の型:int
  • 第1引数の型:const void *
  • 第2引数の型:const void *

つまり、作成する比較関数(qsort 関数の第4引数に渡すアドレスの関数)の戻り値の型と引数の型は上記のようになります。

ですので、関数の大枠だけを書けば下記のようになりますね!

比較関数の大枠
int 関数名(const void *引数名1, const void *引数名2) {
    int ret;

    /* 関数の中身 */

    return ret;
}

あとは、関数名と引数の名前を付け、さらにこの関数の中身を記述してやれば良いだけです。関数名や引数名は、予約語やスコープ内の他の変数・関数の名前と被っていなければなんでも良いです。

ポインタ引数をソート対象のデータの型のポインタに変換する

ただ、2つの引数が const void * 型である点に注意が必要です。

ひとまず const は置いておいて解説すると、引数の型である void * 型は、どんな型のデータでも指すことが可能なポインタの型になります。ですので、引数が void * 型である比較関数は、どんな型のデータであってもアドレスとして受け取ることが可能です。

一方で、void * 型のポインタ変数に対しては、間接演算子(*)や添字演算子([])を利用することができません。つまり、void * 型のポインタ変数では、これらの演算子を利用してポインタの指す先のデータを取得することができないのです(void * 型のポインタに対して間接演算子や添字演算子を利用するとコンパイルエラーになります)。

なので、間接演算子(*)や添字演算子([])を利用してポインタの指す先のデータを取得するためには、一旦引数の型を他の型のポインタに変換する必要があります。

変換先の型は、”ソート対象のデータの型のポインタ” になります。

これは、比較関数のポインタ引数には、ソート対象のデータのいずれかのアドレスが格納されているからです(比較を行うデータのアドレス)。

比較関数の引数ポインタが指すデータを示す図

もっと具体的にいえば、1次元配列をソートする場合は、その配列の型のポインタに変換を行えば良いです。例えば int 型の配列をソートする場合、ポインタ引数を int * 型のデータに変換します。

また、ここまで const は無視して解説してきましたが、実際には引数の型は const void * で const 指定されていますので、変換先の型にも const 指定する方が良いです。

これは、間違ってポインタ引数の指す先のデータを変更してしまわないようにするためです。

さらに、ここまで解説した型の変換は、キャスト演算子 (型名) を利用しても良いですが、単に変換先の型の変数にポインタ引数の値を代入するだけで行うことも可能です。

下記は、int 型の配列をソートする場合に、ポインタ引数 p_data1p_data2 それぞれの値を、const int * 型の変数 p_int1p_int2 に代入する例になります。

比較関数の大枠
int compare(const void *p_data1, const void *p_data2) {
    int ret;
    const int *p_int1 = p_data1;
    const int *p_int2 = p_data2;

    /* 関数の中身 */

    return ret;
}

p_data1p_data2 では間接演算子を利用することはできませんが、p_int1p_int2 では間接演算子を利用することができるので、上記のような代入により、*p_int1*p_int2 よりポインタ引数の指すデータを取得することが可能になります。

この辺りの void * 型や const 指定については下記ページで詳細を解説していますので、詳しく知りたいかたはこちらを参照していただければと思います。

voidとvoid*型の解説ページのアイキャッチ【C言語】void型とvoid*型(void型ポインタ)について解説 constの解説ページアイキャッチ【C言語】constの使い方・メリットを解説

ポインタ引数が指すデータの大小関係に応じて値を返却する

上記により、ポインタ引数が指すデータを間接演算子(or 添字演算子)を利用して取得できるようになったので、あとは2つのポインタ引数が指すデータの大小関係に応じて値を返却してやれば良いです。

この返却する大小関係に応じた値は、昇順ソートを行う場合と降順ソートを行う場合とで異なります。

具体的な違いは下記のようになります(第1引数のポインタが指すデータを “データ1”、第2引数のポインタが指すデータを “データ2” として説明しています)。

  • 昇順ソートする場合
    • データ1 < データ20 より小さい値
    • データ1 > データ20 より大きい値
    • データ1 == データ20 
  • 降順ソートする場合
    • データ1 < データ20 より大きい値
    • データ1 > データ20 より小さい値
    • データ1 == データ20 

要は、昇順ソートと降順ソートとでは、データ1 < データ2 の場合と データ1 > データ2 の場合とで返却する値が逆になります。

昇順ソートの場合

例えば、int 型の配列のデータを “昇順ソート” する際には、下記のようにポインタ引数の指す2つのデータを比較し、その比較結果に応じて値を返却します。

昇順ソート時の値の返却
int compare(const void *p_data1, const void *p_data2) {
    int ret;
    const int *p_int1 = p_data1;
    const int *p_int2 = p_data2;

    if (*p_int1 < *p_int2) {
        ret = -1;
    } else if (*p_int1 > *p_int2) {
        ret = 1;
    } else {
        ret = 0;
    }
    
    return ret;
}

降順ソートの場合

int 型の配列のデータを “降順ソート” する際には、下記のようにポインタ引数の指す2つのデータを比較し、その比較結果に応じて値を返却します。

昇順ソート時の値の返却
int compare(const void *p_data1, const void *p_data2) {
    int ret;
    const int *p_int1 = p_data1;
    const int *p_int2 = p_data2;

    if (*p_int1 < *p_int2) {
        ret = 1;
    } else if (*p_int1 > *p_int2) {
        ret = -1;
    } else {
        ret = 0;
    }
    
    return ret;
}

昇順ソートを行う場合のものと比較して、返却値の符号が逆になっているところがポイントです。

int 型の数値そのものを扱う型であれば、上記のように単純に比較演算子(<>)を利用して比較を行えば良いので簡単ですが、文字列をソートするような場合は、strcmp 関数などを利用して比較を行うことになります。

また、構造体をソートするような場合は、構造体のあるメンバの値に対して比較を行い、大小関係に応じた値を返却することになります。

これらの具体的な処理内容に関しては、次の qsort 関数を利用したソート例の中で紹介していきたいと思います。

スポンサーリンク

qsort 関数を利用したソート例

最後に qsort 関数でソートを行うソースコードをいくつか紹介しておきたいと思います。

このソート例をみていただくことで qsort 関数の使い方の参考にもなると思いますし、また比較関数が自作できるおかげで様々なソートを行うことができるということも実感できると思います。

整数の配列を qsort 関数でソートする

ここまでにも整数の配列を qsort 関数でソートする例は示してきましたが、全てソート対象のデータの型が int だったので、ここでは short 型の配列を qsort 関数でソートする例を示したいと思います。

整数の配列のソート
#include <stdio.h>
#include <stdlib.h>

/* 比較関数 */
int compare(const void *p_data1, const void *p_data2) {
    int ret;
    const short *p_short1 = p_data1;
    const short *p_short2 = p_data2;

    if (*p_short1 < *p_short2) {
        ret = -1;
    } else if (*p_short1 > *p_short2) {
        ret = 1;
    } else {
        ret = 0;
    }

    return ret;

}


int main(void) {

    int i;

    short array[10] = {
        8, 1, 9, 6, 7, 3, 5, 0, 2, 4
    };
    

    /* qsort関数の実行 */
    qsort(&array[0], 10, sizeof(short), compare);
    
    for (i = 0; i < 10; i++) {
        printf("%d, ", array[i]);
    }
    printf("\n");

    return 0;
}

簡単にポイントを説明しておきたいと思います。

ポイント1:ポインタ引数は const short * に変換する

上記の比較関数は、基本的な qsort 関数の利用例で示した int 型の配列をソートする時のものとほぼ変わりません。実質的に異なるのはポインタ引数の変換先の型が const short * に変わったことのみです。

なぜ変換先の型が変わったかというと、これはソート対象のデータの型が short に変化したからです。これにより、比較関数のポインタ引数が指すデータも short 型になりますので、変換先の型も short * に変更しています(さらには比較関数内部で誤ってポインタ引数の指すデータを変更しないように const 指定しています)。

ポイント2:各データのサイズは “short 型のサイズ”

また qsort 関数の第3引数には、ソート対象の各データのサイズを指定する必要があります。つまり、今回はソート対象の各データが short 型なので、short 型のサイズを指定する必要があります(short 型のサイズは一般的には 2 バイトになります)。

型のサイズは sizeof演算子を用いることで取得できるので、上記の例では sizeof(short) により、qsort 関数の第3引数を指定しています。

この例では short 型のサイズを指定していますが、ソート対象の各データのサイズを指定さえすれば良いので、ソート対象の配列 array の中のいずれかの要素、例えば第 0 要素のサイズを sizeof 演算子で取得し、それを qsort 関数の第3引数に指定するのでも良いです(つまり sizeof(array[0]) を指定する)。

文字列の配列を qsort 関数でソートする

文字列の配列を qsort 関数でソートする例は下記のようになります。

文字列の配列のソート
#include <stdio.h>
#include <stdlib.h>
#include <string.h> /* strcmp */

int compare(const void *p_data1, const void *p_data2) {
    const char *p_str1 = p_data1;
    const char *p_str2 = p_data2;

    return strcmp(p_str1, p_str2);
}


int main(void) {

    int i;

    char array[7][256] = {
        "Sunday",
        "Monday",
        "Tuesday",
        "Wednesday",
        "Thursday",
        "Friday",
        "Saturday"
    };

    qsort(&array[0][0], 7, sizeof(array[0]), compare);
    
    for (i = 0; i < 7; i++) {
        printf("%s\n", array[i]);
    }

    return 0;
}

今回紹介する qsort の利用例の中で難易度は一番高いと思います。

ポイントは3つです。

ポイント1:比較には strcmp を利用する

ポイントの1つ目は strcmp を使用しているところです。

文字列の場合は、単なる比較演算子で比較を行うのが大変なので、比較関数 compare では strcmp を使用して比較を行なっています。

strcmp はアルファベット順的に考えて、第1引数の文字列が第2引数の文字列よりも前側に存在する場合に 0 よりも小さい値を、後ろ側に存在する場合に 0 よりも大きい値を、2つの引数の文字列が同じ場合は 0 を返却しますので、compare 関数ではこの strcmp の戻り値をそのまま返却するようにしています。

ちなみに、strcmp の戻り値に -1 を掛けて返却することで、降順ソートを実現することも可能です。

降順ソート時の値の返却
return strcmp(p_str1, p_str2) * (-1);

ポイント2:ポインタ引数は const char * に変換する

ポイントの2つ目は、compare 関数におけるポインタ引数の変換先の型です。

compare 関数が実行された際、p_data1 と p_data2 には配列 array に格納された各文字列の “先頭の文字” の位置のアドレス(つまり char 型のデータのアドレス)が格納されることになりますので、一旦 const char * 型に変換してから strcmp 関数を実行しています。

ポイント3:各データのサイズは “文字の配列のサイズ”

ポイントの3つ目は、qsort の第3引数です。

今回は文字列の配列 array がソート対象であり、この配列 array の各データは文字列です。さらにC言語においては、文字列は “文字の配列” として扱われるため、結局はこの “文字の配列” のサイズを第3引数に指定する必要があります。

文字列をソートする場合のqsort関数の第3引数に指定する値を示す図

その文字の配列のサイズは sizeof(array[0]) で取得できるので、qsort の第3引数には sizeof(array[0]) を指定するようにしています。

配列 array は下記のように宣言しているため、文字の配列のサイズ、すなわち sizeof(array[0])256 バイトとなります。

文字列の配列の宣言
char array[7][256] = {
    "Sunday",
    "Monday",
    "Tuesday",
    "Wednesday",
    "Thursday",
    "Friday",
    "Saturday"
};

さらに、その文字の配列が配列 array には 7 個あるので、第2引数には 7 を指定しています。 

もし、第3引数に単に char 型のサイズを指定してしまうと上手くソートが出来ません。あくまでも qsort 関数の第3引数に指定すべきなのは “ソート対象の各データのサイズ” です。単純に型のサイズを指定すれば良いというものではないので注意してください。

スポンサーリンク

構造体の配列を qsort 関数でソートする

構造体の配列を qsort 関数でソートする例は下記のようになります。構造体としては PERSON というものを定義し、PERSON 型の配列の各データを init 関数でランダムに初期化してからソートを行っています。

構造体の配列のソート
#include <stdio.h>
#include <stdlib.h>
#include <string.h> /* strcmp */
#include <math.h> /* pow */

/* データの個数 */
#define NUM_PEOPLE 10

/* 名前の配列 */
char *names[] = {
    "ichiro", "jiro", "saburo", "shiro", "goro",
    "rokuro", "nanaro", "hachiro", "kuro", "zyuro"
};

typedef struct _PERSON {
    int age;
    int weight;
    int height;
    char name[256];
} PERSON;


static int compare_age(const void *p_data1, const void *p_data2) {
    int ret;
    const PERSON *person1 = p_data1;
    const PERSON *person2 = p_data2;

    if (person1->age < person2->age) {
        ret = -1;
    } else if (person1->age > person2->age) {
        ret = 1;
    } else {
        ret = 0;
    }
    return ret;
}

int compare_name(const void *p_data1, const void *p_data2) {
    int ret;
    const PERSON *person1 = p_data1;
    const PERSON *person2 = p_data2;

    if (strcmp(person1->name, person2->name) < 0) {
        ret = -1;
    } else if (strcmp(person1->name, person2->name) > 0) {
        ret = 1;
    } else {
        ret = 0;
    }
    return ret;
}

int compare_bmi(const void *p_data1, const void *p_data2) {
    int ret;
    const PERSON *person1 = p_data1;
    const PERSON *person2 = p_data2;

    int bmi1 = person1->weight / pow(((double)person1->height / (double)100), 2);
    int bmi2 = person2->weight / pow(((double)person2->height / (double)100), 2);

    if (bmi1 < bmi2) {
        ret = -1;
    } else if (bmi1 > bmi2) {
        ret = 1;
    } else {
        ret = 0;
    }
    return ret;
}

void init(PERSON *people, int num) {
    int i;

    for (i = 0; i < num; i++) {
        /* 乱数を使って適当に初期化 */
        people[i].age = rand() % 100;
        people[i].weight = rand() % 50 + 50;
        people[i].height = rand() % 100 + 100;
        strcpy(people[i].name, names[rand() % 10]);
    }
}

void print(PERSON *people, int num) {
    int i;

    for (i = 0; i < num; i++) {
        printf("people[%d]:\n", i);
        printf("  age    = %d\n", people[i].age);
        printf("  weight = %d\n", people[i].weight);
        printf("  height = %d\n", people[i].height);
        printf("  name   = %s\n", people[i].name);
    }
}

int main(void) {

    PERSON people[NUM_PEOPLE];

    init(people, NUM_PEOPLE);

    print(people, NUM_PEOPLE);

    /* age に対して昇順ソート */

    printf("[ageに対して昇順ソート]\n");
    qsort(people, NUM_PEOPLE, sizeof(people[0]), compare_age);
    print(people, NUM_PEOPLE);

    /* BMI に対して昇順ソート */
    printf("[BMIに対して昇順ソート]\n");
    qsort(people, NUM_PEOPLE, sizeof(PERSON), compare_bmi);
    print(people, NUM_PEOPLE);

    /* name に対して昇順ソート */
    printf("[nameに対して昇順ソート]\n");
    qsort(people, NUM_PEOPLE, sizeof(PERSON), compare_name);
    print(people, NUM_PEOPLE);

    return 0;
}

このソースコードでは、下記の3つの比較関数を用意しています。

  • compare_agePERSON 型の配列のデータを、age メンバに対して昇順ソートするための比較関数
  • compare_namePERSON 型の配列のデータを、name メンバに対して昇順ソートするための比較関数
  • compare_bmiPERSON 型の配列のデータを BMI に対して昇順ソートするための比較関数

ポイント1:メンバの値を参照して比較を行う

構造体の場合は、構造体のどれかのメンバに対してソートを行うのが基本だと思います。つまり比較関数では、構造体のメンバの値の大小関係を比較する必要があります。

で、このメンバにアクセスするためには型が const void * のままではダメなので、比較関数では比較を行う前にソートを行うデータの型である PERSON のポインタ、つまり PERSON * 型の変数にポインタ引数の値を代入するようにしています。

さらに、compare_age においては age メンバ、compare_name においては name メンバの大小関係を比較し、その結果に応じて値を返却するようにしています(name の場合は文字列なので、strcmp によりアルファベット順的に前にあるか後ろにあるかの比較を行なっています)。

ちなみに、単なる構造体ではなく、構造体のポインタからメンバにアクセスするためにはアロー演算子(->)を用いるのが一般的です。

アロー演算子については下記ページで解説していますので、どういった演算子であるかを知りたい方はぜひ読んでみてください(私のサイトで一番人気のあるページです)。

C言語のアロー演算子(->)を分かりやすく、そして深く解説

ポイント2:メンバにないデータに対するソートも可能

compare_agecompare_name は単純に構造体のメンバの値の比較を行なっていますが、別にメンバの値そのものの比較ではなく、メンバの値から求められる他の値を比較するようなこともできます。その例が compare_bmi になります。

compare_bmi では、weight メンバと height メンバの値から BMI を計算し、その BMI の大小関係に応じて値を返却するようにしています。これにより、構造体のメンバにはない BMI に対して配列のデータのソートを行うことが可能です。

ただ、これは比較関数の作り方によって様々なソートを行うことができることを例として示しているだけで、実はソート速度が遅くなるのであまりオススメはしないです。

これは、比較関数で実行される処理の量が増えるからです。この例であれば、BMI を計算するための演算の分、処理量が増えることになります。

データの並びにもよりますが、一般的に ソート対象のデータの数 < 比較回数 となるので、比較関数の中で処理を行うよりかは、ソートを実行する前にあらかじめ必要な処理を行なった結果を構造体のメンバに保持しておく方がソート速度は速いです。

この例であれば、bmi メンバを構造体 PERSON に追加し、BMI の計算結果をその bmi メンバに代入してから qsort 関数を実行し、比較関数の中では bmi メンバの大小比較のみを行なった方がソート速度が速くなります。

その他のソート関数

ここまではクイックソートを行う qsort 関数について解説してきましたが、その他にもソートを行う関数がC言語の標準ライブラリには用意されています。

特に下記の2つについては、qsort 関数と同様の使い方でソートを行うことが可能です。

  • heapsort:ヒープソートによりソートを行う関数
  • mergesort:マージソートによりソートを行う関数

比較関数が必要な点や、その比較関数の作り方、引数の指定は qsort 関数と全く同じです。

ただ下記の2点の違いがあるのでその点だけ注意して使用していただければと思います。

  1. 戻り値の型が int 型である(qsort では void 型)
    • エラー時には -1 が、正常終了時には 0 が返却されます
  2. mergesort 関数の第3引数が sizeof(void *) より小さいとエラーになる
    • なぜこれでエラーになってしまうかの理由はよく分からないです…
    • 64 bit CPU の場合は sizeof(void *) はおそらく 8 になるので、サイズが 4 未満の型の配列のソートは行えないことになります

まとめ

このページではC言語の標準関数である qsort 関数の使い方について解説しました!

データのソートを行いたい場面は割と多いと思いますが、ソートを実装するのはそれなりに大変です。ですが、今回紹介した qsort 関数を利用することで、簡単にソートを実現することができます。しかもどんな型のデータでもソートできるのでかなり便利です。

一見 qsort 関数の引数の型は難しく見えますが、qsort 関数の使い方で解説した内容や、qsort 関数を利用したソート例で示した実例より、割とシンプルに使用できる関数であることが確認できると思います。

また、qsort 関数を実行するためには比較関数が必要になりますので、事前に比較関数を作成してから qsort 関数を実行するようにしましょう。

比較関数を作らなければならない代わりに、qsort 関数では様々なソートを行うことができます。ぜひ比較関数を作成する際には、比較関数の作り方で解説した内容や、qsort 関数を利用したソート例で示した実例を参考にしてみてください!

また、C言語で力試しをしてみたい方は是非この qsort 関数を作成してみてください(引数は実際の qsort 関数のままで)。

void * のポインタの扱いや、コールバック関数の利用など、学べることがかなり多いと思います!

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です