問 題
並べ替えに関する次の記述の ㋐、㋑、㋒ に当てはまるものの組合せとして最も妥当なのはどれか。
「図は、配列 dat［0］～ dat［3］に格納されたデータを昇順に並べ替える方法の一つを表している。図の方法では、まず、dat［2］と dat［3］のデータを比較し、dat［2］のデータが dat［3］のデータより大きければ、データを交換する。続いて、dat［1］と dat［2］のデータを比較し、左のデータが右のデータより大きければ交換するという操作を繰り返す。この方法は、㋐ と呼ばれる。
㋐ を用いれば、図のように配列の要素数が 4 の場合、比較する回数は、㋑ 回である。また、要素数が n の場合、比較する回数は、㋒ 回である。」
正解 (5)
解 説
隣接するデータを比較し「左の方が大きい」場合に交換する というのを順序よく行っています。このような規則に基づく並び替えを「バブルソート」といいます。知っていれば、これで終わりです。正解は 5 です。
ただし、知らなかったり、他の選択肢のソートとの違いが自身ない場合も「選択肢の活用」、「具体的に考える」という公務員試験全般に使える戦術でぜひ正解を選べるようにしておきましょう。
㋒ に注目します。
n = 1 の時を考えてみましょう。n = 1 、つまり要素数が１であれば、並び替えるものがないため「交換は０回」です。ところが、n + 2、n(n + 1)/2 は共に n = 1 の時に 0 になりません。従って誤りです。㋒ が n(n – 1)/2 とわかります。
以上より、正解は 5 です。
コメント