基本情報技術者試験
2002年度 ＝ 平成14年度・秋期
午前
問13
未整列の配列
A
[
i
]（
i
＝1, 2, ... ,
n
）を、次のアルゴリズムで整列する。要素同士の比較回数のオーダを表す式はどれか。
[アルゴリズム]
(1)
A
[1] ～
A
[
n
]の中から最小の要素を探し、それを
A
[1]と交換する。
(2)
A
[2] ～
A
[
n
]の中から最小の要素を探し、それを
A
[2]と交換する。
(3)
同様に、範囲を狭めながら処理を繰り返す。
ア
O
(log
2
n
)
イ
O
(
n
)
ウ
O
(
n
log
2
n
)
エ
O
(
n
2
)
解答
エ
解説
本問で示されているアルゴリズムは
単純選択ソート
であり、その計算量は
n
2
です。
