💡挿入ソート

今回は paiza の「挿入ソート」の問題に挑戦！

🧩 問題概要

・整数の配列が与えられる
→ 要素数 n と、配列 A

・挿入ソートで「昇順」に並び替える
→ 疑似コード通りに実装する

・ただし普通のソートと違うポイント👇
→ 毎回の途中結果を出力する

・具体的には
→ i = 1 〜 n-1 の各ループごとに

・その時点の配列を出力する
→ 「A[i] を挿入し終わった直後」

・出力形式
→ 配列をスペース区切りで1行ずつ
→ 合計で n-1 行

入力例:

5
4 1 3 5 2

出力例:

1 4 3 5 2
1 3 4 5 2
1 3 4 5 2
1 2 3 4 5

✅OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];
rl.on('line', (line) => lines.push(line));

rl.on('close', () => {
    const n = Number(lines[0]);
    const A = lines[1].split(' ').map(Number);
    
    
    function insertion_sort(A, n) { // A : 配列, n : Aの要素数
        for (let i = 1; i <= n - 1; i++) {
            // A[i] を、整列済みの A[0] ~ A[i-1] の適切な位置に挿入する

            // 実装の都合上、A[i] の値が上書きされてしまうことがあるので、予め A[i] の値をコピーしておく
            const x = A[i];
            
            // A[i] の適切な挿入位置を表す変数 j を用意
            let j = i-1;
            
            // A[i] の適切な挿入位置が見つかるまで、A[i] より大きい要素を1つずつ後ろにずらしていく
            while (j >= 0 && A[j] > x) {
                A[j+1] = A[j];
                j--;
            }
            
            // A[i] を挿入
            A[j+1] = x;
            
            // A[0] ~ A[i] が整列済みになった
            // 出力
            console.log(A.join(' '));
        }
    }
    
    
    // 挿入ソートを実行
    insertion_sort(A, n);
});

🔍コードの流れ

・入力を受け取る
→ 1行目で要素数 n、2行目で配列 A を取得

・挿入ソート関数を呼び出す
→ 配列 A と要素数 n を渡す

・左から順番にループ（i = 1 〜 n-1）
→ 「未整列の要素」を1つずつ取り出す

・今の要素を一時保存（x = A[i]）
→ 後で正しい位置に入れるため

・左側（整列済み部分）を後ろからチェック
→ j = i – 1 からスタート

・xより大きい要素を右にずらす
→ 条件：j >= 0 かつ A[j] > x
→ A[j] を A[j+1] にコピーして詰める

・空いた位置に x を挿入
→ A[j+1] = x

・その時点の配列を出力
→ 各ステップの途中経過を表示

・これを最後まで繰り返す
→ 最終的に全体が昇順になる

🔁 挿入ソート(昇順)の処理内容

・配列を2つに分けて考える

・初期状態では A[0] ~ A[0] を「整列済み」、

・A[1] ~ A[n-1] を「未整列」とする。

・i = 1 〜 n-1までループ

・未整列から1つ取り出す（A[i]）

・それを左側の正しい位置に入れる

・そのために
→ 大きい要素を右にずらす

・※ A[0] 側を左、A[n-1] 側を右と表現

・空いた場所に値を入れる

📝まとめ

挿入ソートは、データ列を「整列済み」と「未整列」の2つに分け、「未整列な配列」からデータを1つ取り出し、「整列済み配列」の適切な位置に挿入することを繰り返す手法。