基本情報技術者 一問一答｜B 第205問

解説

挿入ソートは2番目の要素から順に1つずつ取り出し、左側の整列済み部分の適切な位置に挿入していく。{4,1,3,2}では、①1を取り出し4の前に挿入して{1,4,3,2}、②3を取り出し1と4の間に挿入して{1,3,4,2}、③2を取り出し1と3の間に挿入して{1,2,3,4}となり、昇順の{1,2,3,4}が正解である。{4,3,2,1}は降順に整列した誤り、{2,3,4,1}や{1,3,2,4}は挿入位置の決定を途中で誤った不完全な状態である。頻出ポイントは①各ステップ終了時に左側部分が常に整列済みに保たれること、②ほぼ整列済みのデータには高速（最良でO(n)）だが逆順データでは最悪O(n²)になること、③同じO(n²)系のバブルソート・選択ソートと動作過程が異なること、の3点である。