[자료구조] 삽입 정렬

삽입 정렬의 이해

삽입 정렬은 특수한 경우에 매우 빠르게 동작하는 정렬 알고리즘 입니다.

우선 핵심 논리는 다음과 같습니다.

정렬이 된 영역과 정렬이 되지 않은 영역을 나눠서 정렬이 되지 않은 영역에서 정렬이 된 영역으로 하나씩 이동 시킨다.

삽입 정렬의 구현

void InserSort(int arr[], int n)
{
    int i, j;
    int insData;

    for(i = 1; i < n; i++)
    {
        insData = arr[i];

        for(j = i-1; j >= 0; j--)
        {
            if(arr[j] > insData)
                arr[j+1] = arr[j];
            else
                break;
        }
        arr[j+1] = insData;
    }
}

바깥쪽 for문

i가 1에서 시작하는데 이는 맨 앞의 인덱스 0을 무시하기 위함이다. 맨 앞의 요소는 혼자이니까 정렬이 되었다고 간주할 수 있기 때문이다.

안쪽 for문

j = i - 1인 이유는 정렬된 영역의 오른쪽 끝에서부터 시작하기 때문이다. 즉 i는 정렬시킬 요소의 인덱스고 i -1인 j 는 정렬된 영역의 가장 오른쪽에 있는 인덱스이다. 루프를 돌며 정렬 영역의 왼쪽으로 이동하면서 정렬 시킬 요소의 위치를 찾아준다. 찾았다면 안쪽 for문을 빠져나와서
arr[j+1] = insData; 로 적절한 위치에 값을 넣어준다.

삽입 정렬의 성능 평가

삽입 정렬의 빅-오는 O(N^2)이다.
완전 구린 알고리즘이라고 생각할 수 있지만
삽입 정렬은 거의 정렬된 배열에서는 누구보다 빠른 알고리즘이다.
왜냐하면 이미 정렬이 되었다면 반복문에서 break;를 타고 어떠한 연산도 하지 않고 바로 정렬되지 않은 부분만 처리해주기 때문이다.