C言語の基礎 - ソート関数

qsort関数とは

qsort関数は、第1引数に指定された配列を、第4引数に指定された比較関数の規則に沿って並び替える。 第2引数には配列のサイズ、第3引数には配列要素のデータサイズを指定する。

定義の詳細

<syntaxhighlight lang="c++">
#include <stdlib.h>
void qsort(void *base, size_t num, size_t size, int (*compare)(const void *a, const void *b));
第1引数	base     ソート対象の配列
第2引数	num      配列要素の個数
第3引数	size     配列要素のサイズ
第4引数	compare  比較関数(コールバック関数)

// 比較関数
int (*compare)(const void *a, const void *b)
比較関数の状態         戻り値
第1引数の方が小さい	負の値
両方の引数が等しい	0
第1引数の方が大きい	正の値
</source>

qsort関数の使い方

昇順

配列を昇順で整列する方法を下記に記述する。 尚、asc関数は比較関数である。

<syntaxhighlight lang="c++">
// int型の場合
int asc(const void *a, const void *b)
{
   return *(int *)a - *(int *)b;
}

int main()
{
   int a[] = {2, 3, 1};
   qsort(a, sizeof(a) / sizeof(int), sizeof(int), asc);
   printf("%d, %d, %d", a[0], a[1], a[2]);
   // 表示結果 : "1, 2, 3"
}
</source>

<syntaxhighlight lang="c++">
// long型の場合
// long型の演算結果をそのまま比較関数の戻り値に使うと、int型のオーバーフローが発生し、正確な整列が行えなくなるため、注意すること
int asc(const void *a, const void *b)
{
   long *A = (long *)a;
   long *B = (long *)b;
   if (*A > *B) return 1;
   if (*A < *B) return -1;
   return 0;
}

int main()
{
   long a[] = {2, 3, 1};
   qsort(a, sizeof(a) / sizeof(long), sizeof(long), asc);
   printf("%d, %d, %d", a[0], a[1], a[2]);
   // 表示結果 : "1, 2, 3"
}
</source>

<syntaxhighlight lang="c++">
// 文字列の場合
// strcmp関数の戻り値(負の値, 0, 正の値のいずれかを返す)を比較関数側の戻り値として活用するとよい。

int compare_string(const void *a, const void *b)
{
   return strcmp(*(const char **)b, *(const char **)a);
}

int main()
{
   const char *names[] = {"Bob", "Ann", "Chris"};
   qsort(names, 3, sizeof *names, compare_string);
   printf("%s, %s, %s", names[0], names[1], names[2]);
   // 表示結果 : "Ann, Bob, Chris"
}
</source>

<syntaxhighlight lang="c++">
// 構造体の場合
struct tag_PERSON
{
   int person_id;
   const char *person_name;
}PERSON;

int compare_person_id(const void *a, const void *b)
{
   PERSON *A = (PERSON *)a;
   PERSON *B = (PERSON *)b;
   return A->person_id - B->person_id;
}

int main()
{
   PERSON Persons[] = {{2, "Bob"}, {3, "Ann"}, {1, "Chris"}};
   qsort(Persons, 3, sizeof(PERSON), compare_person_id);
   printf("%s, %s, %s", Persons[0].person_name, Persons[1].person_name, Persons[2].person_name);
   // 表示結果: "Chris,Bob,Ann"
}
</source>

降順

<syntaxhighlight lang="c++">
// int型の場合
int desc(const void *a, const void *b)
{
   return *(int *)b - *(int *)a;
}

int main()
{
   int a[] = {2, 3, 1};
   qsort(a, sizeof(a) / sizeof(*a), sizeof(*a), desc);
   printf("%d, %d, %d", a[0], a[1], a[2]);
   // 表示結果 : "3, 2, 1"
}
</source>

<syntaxhighlight lang="c++">
// 文字列の場合
int compare_string(const void *a, const void *b)
{
   return strcmp(*(const char **)a, *(const char **)b);
}

int main()
{
   const char *names[] = {"Bob", "Ann", "Chris"};
   qsort(names, 3, sizeof *names, compare_string);
   printf("%s, %s, %s", names[0], names[1], names[2]);
   // 表示結果 : "Chris, Bob, Ann"
}
</source>