平成20年度春季ソフトウェア開発午後問5

平成20年度春季 ソフトウェア開発技術者試験(SW)の午後問題5は、

• マージソート

に関する問題でした。

• 問題 : 2008h20h_sw_pm1_qs.pdf

プログラム例(h20h_sw_pm5.c)*1

実行結果

$ gcc h20h_sw_pm5.c && ./a.out
1 2 3 4 5 6 7 8

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

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

次のようにプログラムを加筆修正しました。

#include <time.h>

void bubble_sort(int [], int );

void bubble_sort(int a[], int n) {
  int i, j, tmp;
  for (i = 0; i < n - 1; i++) {
    for (j = n - 1; j > i; j--) {
      if (a[j - 1] > a[j]) {
        tmp = a[j - 1];
        a[j - 1] = a[j];
        a[j] = tmp;
      }
    }
  }
}

int main(void) {
  int hnum = 100000, i;
  int arr1[hnum], arr2[hnum];
  clock_t c1, c2;

  srand((unsigned)time(NULL));
  for (i = 0; i < hnum; i++) {
    arr1[i] = arr2[i] = rand();
  }

  c1 = clock();
  merge_sort(arr1, 0, hnum - 1);
  c2 = clock();
  printf("Merge Sort  = %f[s]\n", (double)(c2-c1)/CLOCKS_PER_SEC);

  c1 = clock();
  bubble_sort(arr2, hnum);
  c2 = clock();
  printf("Bubble Sort = %f[s]\n", (double)(c2-c1)/CLOCKS_PER_SEC);
  return 0;
}

実行結果

要素の数を100000個でやってみたのが以下です。

$ gcc h20h_sw_pm5_cmp.c && ./a.out
Merge Sort  = 0.044918[s]
Bubble Sort = 36.233415[s]

以前、ヒープソートとバブルソートでの速度比較を行ったときも、との性能差を肌で感じることができましたが、のアルゴリズムであるマージソートも高速ですね。

関連

• 平成30年度春季基本情報午後問8(ヒープソート)
• 平成26年度秋季応用情報午後問3(マージソート)
• 数学ガール／乱択アルゴリズム - Mae向きなブログ

*1:実装の都合でフローチャートの関数構成と少し変更しています。