ソート（並べ替え）① : 挿入ソート

ソートの定義

順序付け可能なデータの列を、昇順または降順に並び替える操作

順序付け（じゅんじょつけ）	순서 붙이기
昇順（しょうじゅん）	오름 차순
降順（こうじゅん）	내림 차순

---

ソートの事例

• 得点表を元にしてランキングを作成する
• データの集まりから、上位k個を取ってくる
• 貪欲アルゴリズムの前処理

---

挿入ソートの定義

「未整列な配列」からデータを1つ取り出し、「整列済み配列」の適切な位置に挿入する

• 手持ちのトランプを並び替える際

---

挿入ソートのPseudo Code

insertion_sort(A : 配列, n : Aの要素数)
    for i = 1 to n-1
        // A[i] を、整列済みの A[0] ~ A[i-1] の適切な位置に挿入する

        // 実装の都合上、A[i] の値が上書きされてしまうことがあるので、予め A[i] の値をコピーしておく        
        x <- A[i]

        // A[i] の適切な挿入位置を表す変数 j を用意
        j <- i-1

        // A[i] の適切な挿入位置が見つかるまで、A[i] より大きい要素を1つずつ後ろにずらしていく
        while j >= 0 AND A[j] > x
            A[j+1] = A[j]
            j--

        // A[i] を挿入
        A[j+1] <- x

        // A[0] ~ A[i] が整列済みになった

---

挿入ソートの時間複雑度

O(n^2) 

---

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        var arr = Console.ReadLine().Split().Select(int.Parse).ToArray();
        
        for(int i = 1; i < n; i++)
        {
            int x = arr[i];
            int j = i - 1;
            
            // Shift로직!
            while(j >= 0 && arr[j] > x)
            {
                arr[j+1] = arr[j];
                j--;
            }
            
            arr[j+1] = x;
            
            Console.WriteLine(string.Join(" ", arr));
        }
    }
}