Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

平成30年度春季基本情報午後問8

平成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

バブルソートとの速度比較

これだけで終わっては面白くないので、効率の悪いことで有名な O(n^2)アルゴリズムであるバブルソートと速度比較を行ってみました。

次のようにプログラムを変更。

#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]

ヒープソートO(n \log n)アルゴリズムですが、O(n \log n)O(n^2)アルゴリズムではこんなにも性能が違ってくるんですね。アルゴリズムを学ぶことがいかに大切かということが実感できる結果となりました。