Mae向きなブログ

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

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

平成27年度春季 基本情報技術者試験(FE)の午後問題8は、

に関する問題でした。

f:id:rahaema:20190216193126p:plain

プログラム例(h27h_fe_pm8.c)

実行結果

本問で紹介されているクイックソートを応用したアルゴリズム(select関数)がどれ位高速に動作するのか、効率の悪い方法(select_slow関数)と比較してみました。

配列の大きさを100000、3番目に小さい値を検索した結果が以下です。3回実行してみました。上段がクイックソートを応用したアルゴリズム、下段が効率の悪いアルゴリズムによる実行結果です。

$ gcc h27h_fe_pm8.c && ./a.out
34094   0.001247[s]
34094   21.022426[s]
$ ./a.out
83186   0.001020[s]
83186   22.713672[s]
$ ./a.out
77109   0.001389[s]
77109   23.093841[s]

クイックソートO(n\log n)で動作するので効率が良いというのは、よく知られた事実ですが、O(n^{2})アルゴリズムと比較してみると、その性能差をまざまざと実感することができますね。