삽입 정렬(Insertion Sort)

삽입 정렬

삽입 정렬은 정렬이 안된 key값 오른쪽 부분에서 정렬이 된 key값 왼쪽 부분으로 적절한 위치에 삽입하여 정렬하는 방법이다.

#include <iostream>

using namespace std;

void Print(int *arr, int size)
{
    for (int i = 0; i < size; i++)
    {
        cout << arr[i] << " " << flush;
    }
    cout << endl;
}

int main()
{
    int arr[] = { 1, 3, 2, 4, 6, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);

    for (int i = 1; i < n; i++)
    {
        int key = arr[i];
        int j = i;
        for (; j > 0 && arr[j - 1] > key; j--)
        {
            arr[j] = arr[j - 1];

            cout << "Inner : "; 
            Print(arr,n);
        }
        arr[j] = key;

        cout << "Outer : ";
        Print(arr, n);
    }

    cout << endl;

    return 0;
}

키값 바로 왼쪽 요소부터 비교하여 키값보다 비교대상이 작고,
비교할 index가 0보다 크다면 왼쪽 정렬된 배열을 한칸씩 오른쪽으로 shift한다.

output

Outer : 1 3 2 4 6 5 
Inner : 1 3 3 4 6 5 
Outer : 1 2 3 4 6 5 
Outer : 1 2 3 4 6 5 
Outer : 1 2 3 4 6 5 
Inner : 1 2 3 4 6 6 
Outer : 1 2 3 4 5 6