平成30年度春季 基本情報技術者試験(FE)の午後問題8はヒープソートについての問題でした。まさに基本という名にふさわしい題材だと思います。
疑似言語で書かれた問題をC言語にして実行してみました。
h30h_fe_pm8.c
実行結果
$ gcc h30h_fe_pm8.c && ./a.out Before: 15 5 30 60 45 20 10 After : 5 10 15 20 30 45 60
バブルソートとの速度比較
これだけで終わっては面白くないので、効率の悪いことで有名な のアルゴリズムであるバブルソートと速度比較を行ってみました。
次のようにプログラムを変更。
#include <time.h> #include <stdlib.h> void bubbleSort(int data[], int num); void bubbleSort(int data[], int num) { int i, j; for (i = 0; i < num - 1; i++) { for (j = num - 1; j > i; j--) { if (data[j-1] > data[j]) { swap(data, j-1, j); } } } } int main(void) { int hnum = 100000; int data[hnum], heap[hnum]; clock_t c1, c2; srand((unsigned)time(NULL)); for (int i = 0; i < hnum; i++) { data[i] = rand(); } c1 = clock(); heapSort(data, heap, hnum); c2 = clock(); printf("Heap Sort = %f[s]\n", (double)(c2-c1)/CLOCKS_PER_SEC); c1 = clock(); bubbleSort(data, hnum); c2 = clock(); printf("Bubble Sort = %f[s]\n", (double)(c2-c1)/CLOCKS_PER_SEC); return 0; }
実行結果
要素の数を100000個でやってみたのが以下です。
$ gcc h30h_fe_pm8.c && ./a.out Heap Sort = 0.044185[s] Bubble Sort = 40.557902[s]
ヒープソートはのアルゴリズムですが、
と
のアルゴリズムではこんなにも性能が違ってくるんですね。アルゴリズムを学ぶことがいかに大切かということが実感できる結果となりました。
