【C言語】qsort関数 - ソート関数による並び替え

qsort関数

qsort関数は第一引数に指定された配列を、第四引数に指定された比較関数の規則に沿って並び替えます。第二引数には配列のサイズ、第三引数には配列要素のデータサイズを指定します。

定義詳細

#include <stdlib.h>
void qsort(
  void *base, size_t num, size_t size,
  int (*compare)(const void *a, const void *b)
);
第一引数baseソート対象の配列
第二引数num配列要素の個数
第三引数size配列要素のサイズ
第四引数compare比較関数（コールバック関数）
// 比較関数
int (*compare)(const void *a, const void *b)
比較関数の状態戻り値
第一引数の方が小さい負の値
両方の引数が等しい0
第一引数の方が大きい正の値

比較関数のルール

第四引数には、独自定義した比較関数をコールバック関数として渡します。並び替え実行時、比較関数には整列対象の要素が順次、実引数として渡されてきます。

qsort関数は、比較関数の戻り値を元に、各要素を昇順に整列します。一つ目の仮引数の値のほうが小さいに場合には、0より小さい数値を返し、二つ目の仮引数のほうが小さい場合には、0より大きい数値を返す必要があります。両引数の値が同等の場合は0を返します。

正と負の戻り値に対する判断基準を逆転させることで、降順による整列を実現することも可能です。比較関数の第一引数が第二引数より小さい場合には正の値を返し、逆の場合には負の値を返すようにします。

qsort関数の使い方

昇順

配列を昇順で整列する方法です。ascが実際の比較関数となります。

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]); // "123"
}

asc関数の実装は# 比較関数のルールに沿った形となっています。逆に、不等号による比較（return *(int *)a < *(int *)b;）は意図しない結果を招くため利用しないよう注意してください。必ず「正の数」と「負の数」と「0」の３パターンの的確な戻り値を返す必要があります。

long型の場合

long型の演算結果をそのまま比較関数の戻り値に使うと、int型のオーバーフローが発生し、正確な整列が行えなくなるため、注意してください。

int asc(const void *a, const void *b) {
  // 警告: Implicit conversion loses integer precision: 'long' to 'int'
  return *(long *)a - *(long *)b;
}

次のように、より厳格な戻り値を返すようにする必要があります。 

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 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]); // "321"
}

文字列要素の並び替え

文字列オブジェクトに対する並び替えも可能です。strcmp関数の戻り値（負の値, 0, 正の値のいずれかを返す）を比較関数側の戻り値として活用するとよいでしょう。

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"
}

比較関数の注意点と罠

比較関数の仮引数には各要素へのポインタが渡ってきます。文字列要素const char *はダブルポインタ（const char **）として渡ってくることになる点に注意してください。そのため、*(const char **)aによる間接参照が必要となります。

なおstrcmp((const char *)a, (const char *)b)と記述しても警告や実行時エラーが発生しないことがほとんどです。これらはバグの原因にも繋がるため注意してください。

構造体の並び替え

配列の要素が構造体の場合でもソートが可能です。

struct Person {
  int person_id;
  const char *person_name;
};

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

int main() {
  struct Person persons[] = {
    {2, "Bob"}, {3, "Ann"}, {1, "Chris"},
  };
  qsort(persons, 3, sizeof(struct Person), compare_person_id);
  printf("%s,%s,%s", persons[0].person_name, persons[1].person_name, persons[2].person_name);
  // 表示結果: "Chris,Bob,Ann"
}
広告
広告