第２章５１ソートの仕組み（バブルソート）

#C11仕様 #C言語 #ゲームプログラミング

イチからゲーム作りで覚えるC言語

連載ページ一覧へ

第２章５０列挙型（enum）を扱う : PREV

NEXT : 第２章５２ビットフィールドを扱う :

概要

前回はバブルソートというシンプルなソートプログラムを作成して動きを確認してみました。今回は、より高速に動作する、C言語が標準ライブラリで提供してくれているソートの関数 qsort を使って、ソートをしてみましょう。

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言語の仕様) 以降の環境であれば、サポートされています。

qsort_ex.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_使い方

qsort( ソートする配列, ソートする数, 1要素あたりのサイズ, 大小を比較する関数)

この「大小を比較する関数」には、定義した関数そのものを代入します。

例のプログラムでは具体的には以下の sortCompare 関数を代入しています。この関数のルールに従って、昇順や降順でソートをする順番が決まります。

qsort_ex.c

int sortCompare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
};

ソートする順番を決める関数は、こんなルールで定義してね、ということが決まっています。

引数が 2 つあって、void * 型。
戻値は int 型

大小関係を決めるには、関数の中で下のように定義します。

return する値がプラスなら、１つ目の引数の方が大きい
return する値がマイナスなら、２つ目の引数の方が大きい

この return がプラスかマイナスかによって、自動的に qsort 関数は大小をチェックし、要素を並び替えしてくれます。

構造体を使った配列のソート

シンプルな数字ではなく、構造体の配列などをソートする場合について確認してみます。今回はランキングをイメージしたプログラムです。

名前とスコアを持った構造体、Player 型の構造体を定義して、降順でソートしてみます。

qsort_with_struct.c

#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 として下のように定義しています。

qsort_with_struct.c

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 の速度比較

参考として、qsort 関数と自作bubblesort の速度を比較をするプログラムを載せておきます。このプログラムを実行すると、bubblesort 関数、qsort 関数でそれぞれ、データ 256 個、512個、1024個、・・・131072 個を昇順でソートし、それぞれ 3 回実施した平均の時間を表示します。

comp_qsort_bublesort.c

#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