こんにちは、ナナです。
「ソート」とはデータを昇順や降順に並べ替えることを示します。
データを並べ替えるためのアルゴリズムはいくつもありますが、本記事では「クイックソート」と呼ばれる高速な並べ替えができる「qsort関数」の使い方を紹介します。
本記事では次の疑問点を解消する内容となっています。
では、「qsort関数」によるクイックソート方法について学んでいきましょう。
クイックソートを行うための標準ライブラリ関数
C言語ではクイックソートを行うための標準ライブラリ関数が用意されています。
#include <stdlib.h>
void qsort(void * base, size_t num, size_t size, int (* cmpFunc)(const void * n1, const void * n2));「qsort」とはquick（高速）に sort（並べ替える）を省略した名前となっています。。
qsort関数の仕様
配列で構成されたデータを昇順もしくは降順に並べ替えるための関数です。
| includeファイル | stdlib.h |
| 関数仕様 | void qsort(void * base, size_t num, size_t size, int (* cmpFunc)(const void * n1, const void * n2)); |
| 第１引数 | base：並べ替え対象となる配列データへの先頭番地。 |
| 第２引数 | num：並べ替え対象となる配列の要素数。 |
| 第３引数 | size：並べ替え対象のデータ１つ分のバイト数。 |
| 第４引数 | cmpFunc：並べ替えをするための大小比較用関数へのポインタ |
| 戻り値 | なし |
| 特記事項 | 昇順、降順の選択は比較用関数の実装方法次第で変化する。 |
関数ポインタを指定する必要があるちょっと変わったライブラリ関数になっています。
結構複雑な引数構成となっていますね。これにはちゃんと理由があるのです。後ほど解説しましょう！
qsort関数の第４引数で指定する関数ポインタの仕様
第４引数には「どのような比較をしたいか？」の方法を示した関数へのポインタを指定する必要があります。
つまり、次の関数仕様を満たす比較用関数を皆さんが定義する必要があるのです。
| 関数仕様 | int 比較用関数名(const void * n1, const void * n2); |
| 第１引数 | n1：入れ替え対象となる１つ分のデータへのポインタ。 |
| 第２引数 | n2：入れ替え対象となる１つ分のデータへのポインタ。 |
| 戻り値 | 「０」「１」「－１」の３種類を比較結果として返却する。 昇順／降順の要望に従い、次のように判定を行う。 ・昇順：n1>n2のときに１を返却し、n1<n2のときに－１を返却する。 ・降順：n1<n2のときに１を返却し、n1>n2のときに－１を返却する。 ・同一値の場合は「０」を返却する。 |
この比較用関数の使い方は、この後から順に解説していきます。
qsort関数を使ってデータを並べ替えてみよう！
まずは簡単に「qsort関数」の使い方を示しましょう。long型データの配列を並べ替えることを目標とします。
qsort関数を使った昇順並べ替えのサンプルコード
qsort関数を使った簡単なサンプルコードは次のものです。
#include <stdio.h>
#include <stdlib.h>
// 並べ替え基準を示す関数(昇順)
int cmpnum(const void * n1, const void * n2)
{
if (*(long *)n1 > *(long *)n2)
{
return 1;
}
else if (*(long *)n1 < *(long *)n2)
{
return -1;
}
else
{
return 0;
}
}
int main(void)
{
// 並べ替え対象の配列データ
long num[] = { 60, 10, 50, 30, 80, 40 ,20, 90, 70 , 0};
int i;
// クリックソートによる並べ替え
qsort(num, sizeof(num) / sizeof(num[0]), sizeof(long), cmpnum);
// 並べ替え結果の表示
for (i=0 ; i < sizeof(num) / sizeof(num[0]) ; i++)
{
printf("%d\n", num[i]);
}
return 0;
}0
10
20
30
40
50
60
70
80
90結果は見事に昇順にデータが並んでいますね。これがqsort関数ができる並べ替えです。
降順に並べ替えるためのサンプルコード
降順にする場合は比較用関数の判定方法の戻り値を切り替えることで可能となります。
// 並べ替え基準を示す関数(降順)
int cmpnum(const void * n1, const void * n2)
{
if (*(long *)n1 > *(long *)n2)
{
return -1;
}
else if (*(long *)n1 < *(long *)n2)
{
return 1;
}
else
{
return 0;
}
}90
80
70
60
50
40
30
20
10
0並べ替えの方法を示すための関数を別途用意する必要があるのが「qsort関数」の使い方です。
qsort関数の引数構成の必要性と理由の考察
qsort関数には４つの引数が必要となっています。これらの情報がなぜ必要なのかを考察してみましょう。
void qsort(void * base, size_t num, size_t size, int (* cmpFunc)(const void * n1, const void * n2));関数の引数には常に必要性があるのです。
関数を見たときに「なぜ、この情報が必要なのか？」を推測できる力を身に付けておくと、関数を作るときに正しい設計ができるようになります。
qsort関数が提案するコンセプト
関数とは「サービス」であり、サービスを利用してもらうためのコンセプトがあるのです。
qsort関数のコンセプトは
「どのような配列情報でも、クイックソートで並び替えしてあげますよ！」
です。
ここで「qsort関数側」のサービスが考えることは、「どのような情報をもらえれば、どのような配列情報でも並び替えができるようになるか？」です。
その答えこそが関数の引数として必要な情報なのです。
実際の開発業務におけるプログラミングとは、皆さんが誰かが作った関数を使ったり、皆さんが誰かのために関数を作るということなんです。
そんな場面において「どのような情報を受け渡せばよいのか？」を常に考える力が必要です。
第１引数：配列データへのvoid型ポインタが必要な理由
まず、１つ目の引数は配列データへのポインタとなっています。
ポインタが必要な理由は明確ですね。それは、並び替え対象の配列の「場所」を示すためです。場所がわからずして並べ替えなどできるわけがありません。
そして、もう一つの特徴が「void型ポインタ」になっていることです。
qsort関数のコンセプトは「どんな情報でも並べ替える」ですので、「char型の配列」や「double型の配列」といったデータ型を意識してはならないのです。
そのため、汎用ポインタとしての「void型ポインタ」を利用するのです。
void型ポインタについて詳しく知りたい方は『void型の意味と使い方【void型ポインタの扱い方も解説】』を見ておきましょう。
第２引数：配列要素数が必要な理由
C言語において配列データを渡す時は、ポインタに変化してしまうのでした。
この時に困るのが、荷物である配列がいくつ存在するのかわからないことです。そのため、配列へのポインタを関数へ渡す時には「配列要素数」をセットで渡すのがセオリーです。
ポインタと配列の関係性は『ポインタと配列【類似点と相違点から知る正しい扱い方】』を読むと理解できるでしょう。
第３引数：荷物１つ分のデータサイズが必要な理由
第３引数には配列要素１つ分のデータサイズ（バイト数）を指定する必要があります。
これは「どんな情報でも並び替える」というコンセプトにおいて欠かせない情報です。
第１引数において「void型ポインタ」として場所を指定しましたが、「void型」であるがゆえに荷物に大きさがわからないわけです。
この不足した情報を第３引数で解決しているわけです。
１個当たりの荷物の大きさを知ることで、荷物を入れ替えることができるようになります。
第４引数：関数ポインタが必要となる理由
第４引数は関数ポインタになっています。
並べ替えると言っても「どのような情報」を「どのような並び」で並べたいか？というのはqsort関数はわかりません。それを可能にするのが、この関数ポインタなのです。
qsort関数では構造体といった皆さんが作成したデータ型も並べ替えることができます。そのような情報を並べ替えるためには、並び替えるための基準を決定する必要があるのです。
並べ方はqsort関数が決めるのではなく「qsort関数」を利用する皆さんが決定し、関数として指定するのです。
関数ポインタを使い慣れていない方は『関数ポインタ【ポインタを使って関数を呼ぶ仕組み解説】』を見ておきましょう。
qsort関数で構造体の配列を並べ替えてみよう！
「char型」や「int型」などの組み込みデータ型は、ここまで紹介した方法で並べ替えることが可能です。
ここからは皆さんが定義することができる「構造体の配列」を並べ替える方法を紹介しましょう。
構造体の特徴は自由にデータを定義できることであり、通常並べ替えるためには専用の関数を作ることになります。
「qsort関数」の良さは、このような未知の構造体データでも並べ替えることができることです。
構造体データの並べ替えをマスターすれば、qsort関数を使えるようになったと言ってよいでしょう！
構造体のデータ定義
今回サンプルとする構造体は、次のような「氏名」「年齢」「身長」が構造体メンバとして定義された情報を管理しているとしましょう。
// 個人の情報を管理する構造体型の定義
typedef struct
{
char name[32]; // 氏名
short age; // 年齢
double height; // 身長
} S_PERSON;
//
S_PERSON players[] =
{
{"ラファエル・ナダル", 33, 185.6},
{"ノバク・ジョコビッチ", 32, 188.1},
{"ロジャー・フェデラー", 38, 185.4},
{"錦織圭", 29, 178.2},
};この「年齢」と「身長」という２つの数を元に「昇順」「降順」に並べ替えるプログラムパターンを作ってみましょう。
「年齢」による昇順への並べ替え
それでは「年齢」を昇順として並べ替えしてみましょう。
#include <stdio.h>
#include <stdlib.h>
// 個人の情報を管理する構造体型の定義
typedef struct
{
char name[32]; // 氏名
short age; // 年齢
double height; // 身長
} S_PERSON;
//
S_PERSON players[] =
{
{"ラファエル・ナダル", 33, 185.6},
{"ノバク・ジョコビッチ", 32, 188.1},
{"ロジャー・フェデラー", 38, 185.4},
{"錦織圭", 29, 178.2},
};
// 年齢(昇順)
int cmpAscAge(const void * n1, const void * n2)
{
if (((S_PERSON *)n1)->age > ((S_PERSON *)n2)->age)
{
return 1;
}
else if (((S_PERSON *)n1)->age < ((S_PERSON *)n2)->age)
{
return -1;
}
else
{
return 0;
}
}
int main(void)
{
int i;
// クリックソートによる並べ替え
qsort(players, sizeof(players) / sizeof(players[0]), sizeof(S_PERSON), cmpAscAge);
// 並べ替え結果の表示
for (i=0 ; i < sizeof(players) / sizeof(players[0]) ; i++)
{
printf("%-24s, %d, %lf \n", players[i].name, players[i].age, players[i].height);
}
return 0;
}cmpAscAge関数では、構造体メンバである「age」メンバを大小比較して戻り値を決定します。void型ポインタは、キャストを行って正式な構造体を参照できるようにする必要があります。
錦織圭 , 29, 178.200000
ノバク・ジョコビッチ , 32, 188.100000
ラファエル・ナダル , 33, 185.600000
ロジャー・フェデラー , 38, 185.400000「年齢」が昇順に並んでいるのがわかりますね。
「年齢」による降順への並べ替え
それでは「年齢」を降順として並べ替えしてみましょう。
変化させるのは比較用関数と、qsort関数の呼び出し方法です。
// 年齢(降順)
int cmpDescAge(const void * n1, const void * n2)
{
if (((S_PERSON *)n1)->age > ((S_PERSON *)n2)->age)
{
return -1;
}
else if (((S_PERSON *)n1)->age < ((S_PERSON *)n2)->age)
{
return 1;
}
else
{
return 0;
}
}戻り値の結果を逆にすることで降順になります。
「qsort関数」の呼び出し時は第４引数にこの関数を指定します。
qsort(players, sizeof(players) / sizeof(players[0]), sizeof(S_PERSON), cmpDescAge);ロジャー・フェデラー , 38, 185.400000
ラファエル・ナダル , 33, 185.600000
ノバク・ジョコビッチ , 32, 188.100000
錦織圭 , 29, 178.200000「身長」による昇順への並べ替え
それでは次は「身長」を昇順として並べ替えしてみましょう。
// 身長(昇順)
int cmpAscHeight(const void * n1, const void * n2)
{
if (((S_PERSON *)n1)->height > ((S_PERSON *)n2)->height)
{
return 1;
}
else if (((S_PERSON *)n1)->height < ((S_PERSON *)n2)->height)
{
return -1;
}
else
{
return 0;
}
}身長の場合は参照するメンバを「height」に切り替えるだけですね。
錦織圭 , 29, 178.200000
ロジャー・フェデラー , 38, 185.400000
ラファエル・ナダル , 33, 185.600000
ノバク・ジョコビッチ , 32, 188.100000「身長」による昇順への並べ替え
それでは最後に「身長」を降順として並べ替えしてみましょう。ここまでくればもう説明は不要ですね。
// 身長(降順)
int cmpDescHeight(const void * n1, const void * n2)
{
if (((S_PERSON *)n1)->height > ((S_PERSON *)n2)->height)
{
return -1;
}
else if (((S_PERSON *)n1)->height < ((S_PERSON *)n2)->height)
{
return 1;
}
else
{
return 0;
}
}ノバク・ジョコビッチ , 32, 188.100000
ラファエル・ナダル , 33, 185.600000
ロジャー・フェデラー , 38, 185.400000
錦織圭 , 29, 178.200000比較対象の関数ポインタを切り替えることで、柔軟に対象基準の数と昇順／降順を選択できるようになっているのがわかったことでしょう。
これがqsort関数の目指す「どのような配列情報でも、クイックソートで並び替えしてあげますよ！」のコンセプトを実現する方法です。