
前回はバブルソートというシンプルなソートプログラムを作成して動きを確認してみました。 今回は、より高速に動作する、C言語が標準ライブラリで提供してくれているソートの関数 qsort を使って、ソートをしてみましょう。
qsort は QuickSort と呼ばれるソートを行うアルゴリズムの略です。 実際には qsort の中身が QuickSort とは限らないのですが、 重要なのは、 Bubble Sort よりもデータをソートする アルゴリズムが効率化されており、素早く動作する点です。
バブルソートは n 個のデータを処理するために n の 2 乗の処理が必要でしたが、 QuickSort は n 個のデータを O(n × log(n) ) の処理できます。
図にしてみると下のような差があります。
ソートするデータの数が小さければ、大した差はありませんが、 ソートする数が 10,000 個を超えたくらいから、明らかに qsort の方が 早くソートしてくれることがわかります。 (※この処理時間を計算したプログラムは当ページの末尾に補足として記載していますので、 興味があれば、ご自身の環境で実行してみてください!)
qsort 関数を使うために、「stdlib.h」のヘッダーをインクルードして使います。 qsort 関数は C99仕様(1999年のC言語の仕様) 以降の環境であれば、サポートされています。
#include <stdio.h>
#include <stdlib.h>
int sortCompare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
};
int main() {
int scores[] = { -5, 99, 5, 20, 1, 5 };
qsort(scores, 6, sizeof(int), sortCompare);
printf("ソートした結果: ");
for (int n = 0; n < 6; n++) {
printf("%d, ", scores[n]);
}
}
実行した結果は下になります。
ソートした結果: -5, 1, 5, 5, 20, 99,
6 つの int 型配列の要素が昇順でソートされています。
qsort 関数は以下のように使います。
qsort( ソートする配列, ソートする数, 1要素あたりのサイズ, 大小を比較する関数)
この「大小を比較する関数」には、定義した関数そのものを代入します。
例のプログラムでは具体的には以下の sortCompare 関数を代入しています。 この関数のルールに従って、昇順や降順でソートをする順番が決まります。
int sortCompare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
};
ソートする順番を決める関数は、こんなルールで定義してね、ということが決まっています。
大小関係を決めるには、関数の中で下のように定義します。
この return がプラスかマイナスかによって、自動的に qsort 関数は大小をチェックし、 要素を並び替えしてくれます。
シンプルな数字ではなく、構造体の配列などをソートする場合について確認してみます。 今回はランキングをイメージしたプログラムです。
名前とスコアを持った構造体、Player 型の構造体を定義して、降順でソートしてみます。
#include <stdio.h>
#include <stdlib.h>
typedef struct {
char name[64];
int score;
} Player;
int scoreSort(const void* a, const void* b){
Player * tempa = (Player *)a;
Player * tempb = (Player *)b;
return tempb->score - tempa->score;
}
int main() {
Player ps[4] = {
{"ぷらんく",50}
,{"シャロッテ",200}
,{"豆盗賊",10}
,{"ランチおやじ",-10}
};
qsort(ps, 4, sizeof(Player), scoreSort);
for (int i = 0; i < 4; i++) {
printf("ランキング %d 位:%s さん。スコアは %d でした。\n",
i, ps[i].name, ps[i].score);
}
}
実行すると、下のような結果がでました。ちゃんとスコアが高い順番でランキング表がでましたね!
ランキング 0 位:シャロッテ さん。スコアは 200 でした。
ランキング 1 位:ぷらんく さん。スコアは 50 でした。
ランキング 2 位:豆盗賊 さん。スコアは 10 でした。
ランキング 3 位:ランチおやじ さん。スコアは -10 でした。
ソートの判断に使う関数は scoreSort として下のように定義しています。
int scoreSort(const void* a, const void* b){
Player *tempa = (Player *)a;
Player *tempb = (Player *)b;
return tempb->score - tempa->score;
}
void * 型として引数として受け取った要素 a, b は実際には Player 型へのポインタなので、 分かりやすくするために、9~10行目で、(Player *) 型の tempa、tempb にキャストしておきます。
11 行目で、スコア順で降順にソートするためのルールを記載しています。 二つの構造体の score を比較して、大小を決めています。
参考として、qsort 関数と 自作bubblesort の速度を比較をするプログラムを載せておきます。 このプログラムを実行すると、bubblesort 関数、qsort 関数でそれぞれ、データ 256 個、512個、1024個、・・・131072 個を昇順でソートし、それぞれ 3 回実施した平均の時間を表示します。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
int sortCompare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
};
double getRunTime_qsort(int n) {
clock_t start, end;
int* data = (int*)malloc(n * sizeof(int));
time_t t;
srand((unsigned)time(&t));
for (int i = 0; i < n; i++) {
data[i] = rand() % 2048;
}
start = clock();
qsort(data, n, sizeof(int), sortCompare);
end = clock();
free(data);
double cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
return cpu_time_used;
}
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
double getRunTime_bubblesort(int n) {
clock_t start, end;
int* data = (int*)malloc(n * sizeof(int));
time_t t;
srand((unsigned)time(&t));
for (int i = 0; i < n; i++) {
data[i] = rand() % 2048;
}
start = clock();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (data[j] > data[j + 1]) {
swap(&data[j], &data[j + 1]);
}
}
}
end = clock();
free(data);
double cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
return cpu_time_used;
}
int main() {
puts("bubblesort:");
for (int i = 8; i < 18; i++) {
double ave = 0;
int n = pow(2, i);
for (int u = 0; u < 3; u++) {
ave += getRunTime_bubblesort(n);
}
ave = ave / 3;
printf("%d,%f\n", n, ave);
}
puts("qsort:");
for (int i = 8; i < 18; i++) {
double ave = 0;
int n = pow(2, i);
for (int u = 0; u < 3; u++) {
ave += getRunTime_qsort(n);
}
ave = ave / 3;
printf("%d,%f\n", n, ave);
}
}
実行した結果は下のようになりました。 単位は秒です!
ソートするデータ量 | bubblesort(秒) | qsort(秒) |
---|---|---|
256 | 0.000667 | 0.000000 |
512 | 0.003333 | 0.000333 |
1024 | 0.007333 | 0.000333 |
2048 | 0.050333 | 0.001000 |
4096 | 0.144333 | 0.001667 |
8192 | 0.667000 | 0.003667 |
16384 | 2.463667 | 0.007000 |
32768 | 8.693000 | 0.013333 |
65536 | 38.558000 | 0.021667 |
131072 | 72.000000 | 0.047333 |
結果をみると、データ量の数にかかわらず、常に qsort を使った方が早かったです。
実行したパソコンの環境は以下の通りです。
コメント、ありがとうございます。
ごめんなさい。エラーでうまく送信できませんでした。ご迷惑をおかけします。しばらくおいてから再度送信を試していただくか、以下から DM などでご連絡頂ければと思います。
Twitter:@NodachiSoft_jpお名前:以下の内容でコメントを送信します。よろしければ、「送信」を押してください。修正する場合は「戻る」を押してください
お名前: