BohYoh.com《第２種情報処理技術者試験》1996年度＝平成8年度・秋期午前問8

第２種情報処理技術者試験

1996年度＝平成8年度・秋期

午前

問8

　次の流れ図が表す整列アルゴリズムはどれか。

ア　クイックソート	イ　シェーカソート	ウ　シェルソート
エ　挿入ソート	オ　バブルソート

解答

　オ

解説

　バブルソートでは、隣り合うデータを比較し、必要であれば交換を行うという一連の操作（パス）をn - 1回行います。

１パス目　　　┌─┬─┬─┬─┬─┬─┐ 　　　│５│４│１│３│６│２│　　　　最初の状態　　　└─┴─┴─┴─┴─┴─┘ 　　　　└─┘ 　　　　　　　　　　　　　　　　　　↓　比較・交換　　　┌─┬─┬─┬─┬─┬─┐ 　　　│４│５│１│３│６│２│ 　　　└─┴─┴─┴─┴─┴─┘ 　　　　　　└─┘ 　　　　　　　　　　　　　　　　　　↓　比較・交換　　　┌─┬─┬─┬─┬─┬─┐ 　　　│４│１│５│３│６│２│ 　　　└─┴─┴─┴─┴─┴─┘ 　　　　　　　　└─┘ 　　　　　　　　　　　　　　　　　　↓　比較・交換　　　┌─┬─┬─┬─┬─┬─┐ 　　　│４│１│３│５│６│２│ 　　　└─┴─┴─┴─┴─┴─┘ 　　　　　　　　　　└─┘ 　　　　　　　　　　　　　　　　　　↓　比較・交換の必要なし　　　┌─┬─┬─┬─┬─┬─┐ 　　　│４│１│３│５│６│２│ 　　　└─┴─┴─┴─┴─┴─┘ 　　　　　　　　　　　　└─┘ 　　　　　　　　　　　　　　　　　　↓　比較・交換　　　┌─┬─┬─┬─┬─┬─┐ 　　　│４│１│３│５│２│６│ 　　　└─┴─┴─┴─┴─┴─┘ ２パス目　　　┌─┬─┬─┬─┬─┬─┐ 　　　│４│１│３│５│２│６│ 　　　└─┴─┴─┴─┴─┴─┘ 　　　　└─┘ 　　　　　　　　　　　　　　　　　　↓　比較・交換　　　┌─┬─┬─┬─┬─┬─┐ 　　　│１│４│３│５│２│６│ 　　　└─┴─┴─┴─┴─┴─┘ 　　　　　　└─┘ 　　　　　　　　　　　　　　　　　　↓　比較・交換　　　┌─┬─┬─┬─┬─┬─┐ 　　　│１│３│４│５│２│６│ 　　　└─┴─┴─┴─┴─┴─┘ 　　　　　　　　└─┘ 　　　　　　　　　　　　　　　　　　↓　比較・交換の必要なし　　　┌─┬─┬─┬─┬─┬─┐ 　　　│１│３│４│５│２│６│ 　　　└─┴─┴─┴─┴─┴─┘ 　　　　　　　　　　└─┘ 　　　　　　　　　　　　　　　　　　↓　比較・交換　　　┌─┬─┬─┬─┬─┬─┐ 　　　│１│３│４│２│５│６│ 　　　└─┴─┴─┴─┴─┴─┘ 　　　　　　　　　　　　└─┘ 　　　　　　　　　　　　　　　　　　↓　比較・交換の必要なし　　　┌─┬─┬─┬─┬─┬─┐ 　　　│１│３│４│２│５│６│ 　　　└─┴─┴─┴─┴─┴─┘ …（以降省略）…

※１パスが終了した時点で、最も大きい値が配列の最後に位置しますから、２パス目の最後の比較・交換作業は省略することができます。