
挿入ソートで整列済みの範囲を追う
挿入ソートの途中では、配列の全部が整っているわけではありません。「どこまでが整列済みか」と「挿入する値をどこへ退避したか」を一緒に追います。
用語の正確な意味
挿入ソートは、整列済みの部分列に未処理の要素を一つずつ適切な位置へ挿入していく整列法です。ここでは昇順、要素番号は1始まりとし、i番目の値を左側の整列済み部分へ挿入します。
ざっくりした意味と使いどころ
左手のカードを小さい順に並べ、新しいカードを間へ差し込むイメージです。少数のデータや、ある程度並んだデータを扱うときに使われます。逆順のような場合には移動が多くなり、処理回数は要素数nの二乗に比例する規模になります。
手順を追う例
A=[6, 2, 5, 3]から始めます。最初は先頭の6だけを整列済みとみなします。
i=2:値2を変数keyへ退避し、6を右へ移動してから2を挿入。結果は[2, 6, 5, 3]。
i=3:key=5。6を右へ移動し、2の右へ5を挿入。結果は[2, 5, 6, 3]。
i=4:key=3。6、5を順に右へ移動し、2の右へ3を挿入。結果は[2, 3, 5, 6]。
移動の途中では同じ値が二か所に見える瞬間があります。退避したkeyを最後に書き戻すので、値は失われません。
確認問題【オリジナル】
A=[7, 4, 6, 2]を同じ方法で昇順に整列します。i=3の挿入が終わった直後の配列はどれでしょうか。
ア:[4, 6, 7, 2]
イ:[2, 4, 6, 7]
ウ:[4, 7, 6, 2]
エ:[7, 4, 2, 6]
正解と選択肢の見方
正解はアです。i=2で[4, 7, 6, 2]になり、i=3では6を退避して7を一つ右へ動かし、4の右に6を入れます。末尾の2はまだ処理していません。
イは全処理が終わった状態で、一段階先まで進めすぎです。ウはi=2の処理後なので一段階手前です。エは未処理部分を交換しており、今回の挿入手順とは一致しません。
問題を解くときの確認点
外側のループのi、退避するkey、右へ動かす位置jを別々に書きます。比較が「A[j]>key」なら同じ値を追い越さず、この手順は安定な整列になります。「以上」に変えると、同じ値の元の順番を保てない場合があります。
本記事の例と確認問題は独自に作成しています。