C言語でqsort/qsort_r関数の使い方を教えて！
こういった悩みにお答えします．
本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Verse（UEFN）, Assembler (x64，aarch64)．
- 東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
- 2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
- 最近は自然言語処理AIとイーサリアムに関する有益な情報発信や，Unreal Editor for Fortnite（UEFN）でゲーム開発に従事．
- （AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でChatGPT/Geminiを訓練するプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
- （スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
- UEFNで10本以上のゲームを開発し，フォートナイト上で公開（Fortnite，Fortnite.GG）．
こういった私から学べます．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
目次
qsort関数
|
1 2 |
void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)); |
qsort関数は，nmemb個の大きさsizeの要素をもつ配列を並び替える関数です．
※配列を並び替える方法は，主にクイックソートを利用しています．
base引数は配列の先頭へのポインタです．
comparをポインタとする比較関数により，配列の中身は昇順 (値の大きいものほど後に並ぶ順番) にソートされます．
比較関数の引数は比較される2つのオブジェクトのポインタです．
比較関数は，第1引数が第2引数と比較して，小さい，等しい，大きい場合，それぞれ0より小さい整数，0，0より大きい整数を返さなければなりません．
2つの要素の比較結果が等しい場合，並び替える後の配列で，2つの要素の順序は規定されていません．
つまり，qsort関数は安定ソートではなく不安定ソートになります．
qsort関数の使い方
qsort関数の使い方は以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> int arraycmp(const void *p1, const void *p2) { return *(const int *) p1 > *(const int *) p2; } void print_array(size_t n, int array[]) { size_t i; for (i = 0; i < n; i++) { printf("%d ", array[i]); } printf("\n"); } int main(void) { int array[] = {11, -100, 33, 22, 567, -44, 77}; size_t n = sizeof(array) / sizeof(array[0]); printf("Before: "); print_array(n, array); qsort(array, n, sizeof(int), arraycmp); printf("After: "); print_array(n, array); return 0; } |
実行結果は以下になります．
|
1 2 3 4 |
$ gcc qsort.c $ a.out Before: 11 -100 33 22 567 -44 77 After: -100 -44 11 22 33 77 567 |
qsort関数の問題点
qsort関数の問題点は，比較関数に任意の引数を渡したい場合，グローバル変数を利用しなければならないことです．
一般的にグローバル変数の利用は，保守性の観点からできる限り避けるべきと言われています．
qsort関数の比較関数内で比較回数と第1引数が第2引数より大きい回数をカウントするコードは以下になります．
15行目でグローバル変数のint型の配列numsを定義し，比較関数arraycmpでアクセスしています．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #define _GNU_SOURCE #include <stdio.h> #include <stdlib.h> enum { NR_COMPARES = 0, NR_GREATERS = 1, ARRAY_NUM = 2 }; int nums[ARRAY_NUM] = {0}; int arraycmp(const void *p1, const void *p2) { int greater = *(const int *) p1 > *(const int *) p2; nums[NR_COMPARES]++; if (greater) { nums[NR_GREATERS]++; } return greater; } void print_array(size_t n, int array[]) { size_t i; for (i = 0; i < n; i++) { printf("%d ", array[i]); } printf("\n"); } int main(void) { int array[] = {11, -100, 33, 22, 567, -44, 77}; size_t n = sizeof(array) / sizeof(array[0]); printf("Before: "); print_array(n, array); qsort(array, n, sizeof(int), arraycmp); printf("After: "); print_array(n, array); printf("# of compares = %d\n", nums[NR_COMPARES]); printf("# of greaters = %d\n", nums[NR_GREATERS]); return 0; } |
実行結果は以下になります．
比較回数が13，第1引数が第2引数より大きい回数が5になりました．
|
1 2 3 4 5 6 |
$ gcc qsort2.c $ a.out Before: 11 -100 33 22 567 -44 77 After: -100 -44 11 22 33 77 567 # of compares = 13 # of greaters = 5 |
qsort_r関数
|
1 2 3 |
void qsort_r(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *, void *), void *arg); |
qsort_r関数はqsort関数と似ていますが，比較関数comparが第3引数としてvoid型のポインタを取る点と，その第3引数がqsort_r関数の第5引数のarg経由で比較関数に渡される点が異なります．
これにより，比較関数は任意の引数を渡すためにグローバル変数を利用する必要がなくなり，リエントラント（再入可能） になります．
qsort_r関数の比較関数内で比較回数と第1引数が第2引数より大きい回数をカウントするコードは以下になります．
45行目でローカル変数のint型の配列numsを定義し，qsort_r関数の第5引数として渡すことで，比較関数arraycmpでアクセスしています．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #define _GNU_SOURCE #include <stdio.h> #include <stdlib.h> enum { NR_COMPARES = 0, NR_GREATERS = 1, ARRAY_NUM = 2 }; int arraycmp(const void *p1, const void *p2, void *arg) { int *nums = (int *) arg; int greater = *(const int *) p1 > *(const int *) p2; nums[NR_COMPARES]++; if (greater) { nums[NR_GREATERS]++; } return greater; } void print_array(size_t n, int array[]) { size_t i; for (i = 0; i < n; i++) { printf("%d ", array[i]); } printf("\n"); } int main(void) { int array[] = {11, -100, 33, 22, 567, -44, 77}; size_t n = sizeof(array) / sizeof(array[0]); int nums[ARRAY_NUM] = {0}; printf("Before: "); print_array(n, array); qsort_r(array, n, sizeof(int), arraycmp, nums); printf("After: "); print_array(n, array); printf("# of compares = %d\n", nums[NR_COMPARES]); printf("# of greaters = %d\n", nums[NR_GREATERS]); return 0; } |
実行結果は以下になります．
グローバル変数を利用しないで，比較回数が13，第1引数が第2引数より大きい回数が5と計算できました．
|
1 2 3 4 5 6 |
$ gcc qsort_r.c $ a.out Before: 11 -100 33 22 567 -44 77 After: -100 -44 11 22 33 77 567 # of compares = 13 # of greaters = 5 |
まとめ
C言語でqsort/qsort_r関数の使い方を紹介しました．
特にqsort_r関数はグローバル変数を利用しないで比較関数に任意の引数を渡せることがわかりました．
クイックソートを含むソート関数の自作を知りたいあなたはこちらからどうぞ．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
