Nodachisoft Nodachi Sword Icon
  
@あまじ✎ 2021年3月7日に更新

第2章51 ソートの仕組み(バブルソート)

イチからゲーム作りで覚えるC言語
第2章50 列挙型(enum)を扱う : PREV
NEXT : 第2章52 ビットフィールドを扱う :

概要

前回はバブルソートというシンプルなソートプログラムを作成して動きを確認してみました。 今回は、より高速に動作する、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 する値がプラスなら、1つ目の引数の方が大きい
  • return する値がマイナスなら、2つ目の引数の方が大きい

この 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

結果をみると、データ量の数にかかわらず、常に qsort を使った方が早かったです。

実行したパソコンの環境は以下の通りです。

  • CPU : Intel Core i7-8565U CPU @ 1.80GHz
  • メモリ : 8.0 GB
  • OS : Windows10 64bit (Version 2004)

参考文献

  • 特になし
イチからゲーム作りで覚えるC言語
第2章50 列挙型(enum)を扱う : PREV
NEXT : 第2章52 ビットフィールドを扱う :
 
 
送信しました!

コメント、ありがとうございます。

なんかエラーでした

ごめんなさい。エラーでうまく送信できませんでした。ご迷惑をおかけします。しばらくおいてから再度送信を試していただくか、以下から DM などでご連絡頂ければと思います。

Twitter:@NodachiSoft_jp
お名前:
 
連絡先:
 
メッセージ:
 
戻る
内容の確認!

以下の内容でコメントを送信します。よろしければ、「送信」を押してください。修正する場合は「戻る」を押してください

お名前:
 
連絡先:
 
メッセージ:
 
Roboto からの操作ではないという確認のため確認キーを入れてください。
確認キー=95
戻る
 / 
送信確認へ
コメント欄
コメント送信確認へ

関連ありそうな記事(5件)です!

第4章3 C言語コンソール上で迷路脱出プログラム・迷路の自動生成

#C11仕様#C言語#ゲームプログラミング✎ 2021-05-15
C言語のコンソールゲームで迷路脱出ゲームプログラムの作り方を確認します。迷路は自動生成されます
広告領域
追従 広告領域
目次
第2章51 ソートの仕組み(バブルソート)
第2章51 ソートの仕組み(バブルソート)
概要
概要
qsort とは
qsort とは
使用例
使用例
構造体を使った配列のソート
構造体を使った配列のソート
参考:qsort と bubblesort の速度比較
参考:qsort と bubblesort の速度比較
参考文献
参考文献
Nodachisoft © 2021