qsort の利用
標準ライブラリのソートです。
「qsort の利用」はCoddyKit上の無料C Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。
標準ライブラリのソート
Cの標準ライブラリには、<stdlib.h>のqsortが用意されています。比較関数を指定すれば任意の配列をソートできるため、独自のソートを書く必要はほとんどありません。
qsortのシグネチャ
プロトタイプは次のとおりです。
base先頭要素へのポインタnmemb要素数size1要素あたりのバイト数compar比較関数へのポインタ
void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
比較関数を書く
比較関数は2つのconst void *を受け取ります。実際の型にキャストしてデリファレンスし、負の値、0、正の値のいずれかを返します。
#include <stdio.h>
#include <stdlib.h>
int cmp_int(const void *a, const void *b) {
int x = *(const int *)a;
int y = *(const int *)b;
return (x > y) - (x < y); /* safe, no overflow */
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
qsort(a, 5, sizeof(int), cmp_int);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}比較関数で減算を避ける
x - yを返すと、大きな整数ではオーバーフローが発生し、誤った結果になる可能性があります。代わりに、真偽値の差を使う慣用表現(x > y) - (x < y)を使用してください。
#include <stdio.h>
int main(void) {
int x = 2000000000, y = -2000000000;
printf("unsafe x-y = %d\n", x - y); /* overflow */
printf("safe = %d\n", (x > y) - (x < y));
return 0;
}降順
降順にソートするには、比較結果を反転するだけです。
#include <stdio.h>
#include <stdlib.h>
int cmp_desc(const void *a, const void *b) {
int x = *(const int *)a, y = *(const int *)b;
return (y > x) - (y < x);
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
qsort(a, 5, sizeof(int), cmp_desc);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}文字列のソート
char *の配列をソートする場合、比較関数はポインタへのポインタを受け取ります。const char * const *にキャストして、strcmpを呼び出してください。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmp_str(const void *a, const void *b) {
const char *x = *(const char * const *)a;
const char *y = *(const char * const *)b;
return strcmp(x, y);
}
int main(void) {
const char *names[] = {"charlie", "alice", "bob"};
qsort(names, 3, sizeof(char *), cmp_str);
for (int i = 0; i < 3; i++) printf("%s ", names[i]);
printf("\n");
return 0;
}構造体のソート
構造体の配列は、任意のフィールドを基準にソートできます。ここでは、年齢順に人物を並べます。
#include <stdio.h>
#include <stdlib.h>
typedef struct { char name[16]; int age; } Person;
int by_age(const void *a, const void *b) {
const Person *p = a, *q = b;
return (p->age > q->age) - (p->age < q->age);
}
int main(void) {
Person ppl[] = {{"Ann", 30}, {"Ben", 25}, {"Cid", 40}};
qsort(ppl, 3, sizeof(Person), by_age);
for (int i = 0; i < 3; i++) printf("%s %d\n", ppl[i].name, ppl[i].age);
return 0;
}複数キーによるソート
同順位を解消するには、最初のフィールドが等しい場合に2番目のフィールドを比較します。これにより、年齢順、次に名前のアルファベット順でソートできます。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct { char name[16]; int age; } Person;
int cmp(const void *a, const void *b) {
const Person *p = a, *q = b;
if (p->age != q->age)
return (p->age > q->age) - (p->age < q->age);
return strcmp(p->name, q->name);
}
int main(void) {
Person ppl[] = {{"Zoe", 30}, {"Amy", 30}, {"Bo", 25}};
qsort(ppl, 3, sizeof(Person), cmp);
for (int i = 0; i < 3; i++) printf("%d %s\n", ppl[i].age, ppl[i].name);
return 0;
}qsortは安定ではない
C標準では、qsortが安定であることを要求していません。安定性が必要な場合は、元のインデックスなどのタイブレーク用キーを比較関数に追加してください。
bsearchとの組み合わせ
bsearchは、同じ形式の比較関数を使ってソート済み配列を二分探索します。qsortと組み合わせると、高速に検索できます。
#include <stdio.h>
#include <stdlib.h>
int cmp_int(const void *a, const void *b) {
int x = *(const int *)a, y = *(const int *)b;
return (x > y) - (x < y);
}
int main(void) {
int a[] = {1, 3, 5, 7, 9};
int key = 7;
int *found = bsearch(&key, a, 5, sizeof(int), cmp_int);
printf("%s\n", found ? "found" : "missing");
return 0;
}qsortを使う理由
標準のqsortは十分にテストされており、多くの場合は調整済みのintrosortハイブリッドで、任意の型に対応できます。安定性や、ライブラリでは実現できない特殊な動作が必要な場合にだけ、独自のソートを実装してください。
理解度チェック
qsortについての理解度を確認しましょう。
まとめ
標準ライブラリのソートの使い方を学びました。
qsort(base, nmemb, size, compar)で任意の配列をソートできる- 比較関数では
const void *をキャストし、比較結果の符号を返す - 減算を避け、
(x > y) - (x < y)を使う qsortの安定性は保証されず、bsearchが対応する検索機能である
よくある質問
「qsort の利用」レッスンは無料ですか？
はい。「qsort の利用」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。
「qsort の利用」で何を学びますか？
標準ライブラリのソートです。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
C Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「qsort の利用」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このC Academyレッスンでコードを書いて実行できますか？
はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- バブルソートと挿入ソート
- クイックソート
- マージソート
- qsort の利用