問題 No.2164
未整理のデータの中から順に要素を取り出し、すでに整列済みの適切な位置に挿入していくことで全体を並び替える代表的な整列アルゴリズムはどれか。
【正解の解説】
挿入法（挿入ソート）
これはトランプのカードを手札に順番に並べ替える動作と全く同じです。新しいカードを手に取るたびに、すでにきれいに並べられた手札の適切な隙間にスッと差し込んでいく様子をイメージしてください。データ量が少ない場合には非常に効率よく動作する身近な整列方法です。
スポンサーリンク
【その他の選択肢の解説】
隣接する要素同士の大小比較を繰り返し行いながら順次交換していくことで全体を並び替える代表的な整列アルゴリズム
挿入ソートが「適切な場所を探して差し込む」のに対し、こちらは「隣同士を比べて入れ替える」という動作を繰り返します。水底から泡がボコボコと浮かび上がるように大きな値が端へ移動していく様子から名付けられたバブルソートの仕組みであり、今回の問題の正解ではありません。
未整理のデータの中から最小または最大の要素を繰り返し探索して先頭から順に配置していくことで全体を並び替える代表的な整列アルゴリズム
全体の中から一番小さなカードを毎回探し出して先頭に持ってくるのが選択ソートの特徴です。すでに並び替えられた場所へ割り込んでいく挿入ソートとは異なり、常に全体の未整理部分から極値を探す点や、データの並びに関わらず一定の計算量がかかる点が決定的な違いです。
全体のデータをあらかじめ中央の基準値で二つの部分に分割してからそれぞれを独立して並び替える代表的な整列アルゴリズム
基準となる値を一つ決めて、それより小さいグループと大きいグループにパパッと分けていく効率的な手法です。一件ずつ順番に位置を探っていく挿入ソートとは異なり、大きなデータを高速に処理できる分割統治法に基づいている点が異なるため注意が必要です。