流れ図の整列アルゴリズム
出典: 令和4年度 秋期 応用情報技術者試験 午前 問6 (IPA)
未整列の配列 A[i] (i＝1，2，…，n) を，次の流れ図によって整列する。ここで用いられる整列アルゴリズムはどれか。
- ア クイックソート
- イ 選択ソート
- ウ 挿入ソート
- エ バブルソート
正解と解説を見る
正解: エ
- ア: クイックソートは基準値 (ピボット) で分割していく方法で、隣同士の比較・交換を繰り返すものではありません。
- イ: 選択ソートは、未整列部分から最小値を探して、最後に 1 回だけ交換する方法です。
- ウ: 挿入ソートは、整列済み部分の適切な位置に要素を挿入していく方法です。
- エ: 隣り合う要素を比較して交換し、小さい値を先頭へ移していくのはバブルソートなので正しい答えです。
ポイント
- ループ 2 では、j を末尾 (n) から先頭側 (i ＋ 1) へ動かしながら、隣り合う A[j] と A[j−1] を比べ、A[j] の方が小さければ交換しています。
- これで最小の値が先頭側へ浮かび上がっていきます。隣同士の比較・交換を繰り返すのは バブルソート です。