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

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

• 与えられたn個のデータの中からk番目に小さい値を選択する方法として、クイックソートを応用したアルゴリズム

に関する問題でした。

• 問題 : 2015h27h_fe_pm_qs.pdf

プログラム例(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]

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