[Algorithm] 삽입 정렬 (Insertion Sort)

Insertion Sort

• 정렬된 부분과 정렬되지 않은 부분으로 나눔
• 정렬 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하는 것을 반복
• 정렬된 배열을 유지하면서 진행
• 맨 처음 원소는 정렬되었다고 가정하고 시작함

코드

#include <iostream>

void Print(int* arr)
{
    for (int i = 0; i < 10; i++)
    {
        std::cout << arr[i] << " ";
    }
    std::cout << "\n";
}

void InsertionSort(int* arr)
{
    for (int i = 1; i < 10; i++)
    {
        int pivot = arr[i];
        int j = i - 1;
        
        while (arr[j] > pivot && j >= 0)
        {
            arr[j+1] = arr[j]; // 오른쪽으로 당김
            j--;
        }
        
        arr[j+1] = pivot;
    }
}

int main()
{
    std::cin.tie(0);
    std::ios::sync_with_stdio(0);

    int arr[10] = {8, 31, 48, 73, 3, 65, 20, 29, 11, 15};

    Print(arr);
    InsertionSort(arr);
    Print(arr);
}

시간 복잡도

평균과 최악 모두 O(n^2)의 시간 복잡도를 가진다.

참고사항

• 정렬된 부분 배열을 유지하고, 그 부분 배열을 하나씩 늘려가며 정렬함
• 입력 상태에 따라 수행시간이 달라짐 -> 거의 정렬된 상태면 빠르고, 역순으로 입력됐다면 매우 느림