[ 알고리즘 / 정렬 ] 삽입 정렬 (Insertion Sort)

삽입 정렬 (Insertion Sort)이란?

- 선택 정렬과 유사하지만, 좀 더 효율적인 알고리즘이다.

- 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

- 매 순서마다 해당 원소를 삽입할 위치를 찾고 해당 위치에 넣는 방식이다.

 

 Process 

① 처음 Target 값은 두 번째 원소부터 시작한다. 두 번째 원소부터 앞의 원소들과 비교하여 삽입할 위치를 찾는다.

② 찾은 위치부터 자료를 뒤로 밀고 그 자리에 해당 원소를 삽입한다.

 Code 

void InsertSort(int Data[], int Lenght)
{
    for(int i = 1; i < Lenght; i++)
    {
        int j, Target = Data[i];
        for(j = i - 1; j >= 0 && Data[j] > Target; j--)
        {
            Data[j + 1] = Data[j];
        }
        Data[j + 1] = Target;
    }
}

 시간복잡도 

최악의 경우 (역으로 정렬)

- (n-1) + (n-2) + (n-3) + ... + 2 + 1 = n (n-1) / 2 이므로 O(n^2)이다.

 

최선의 경우 (이미 정렬)

- 모두 한 번씩 밖에 비교를 안하므로 O(n)이다.

 공간복잡도 

주어진 배열 안에서 교환하기 때문에, O(n)이다.

 장점 

- 알고리즘이 단순하다.

- 연속적인 공간을 참조하기에 참조 지역성이 높아서 성능이 좋다.

- 정렬하고자 하는 배열 안에서 교환하기 때문에, 다른 메모리 공간을 필요로 하지 않는다 => 제자리 정렬(in-place sorting)

- 거품 정렬, 선택 정렬 O(n^2) 보단 상대적으로 빠르다.

- 안정 정렬이다.

 단점 

- 시간복잡도가 최악의 경우 O(n^2)으로, 굉장히 비효율적이다.

- 배열의 길이가 길어질수록 비효율적이다.

 

 정렬 알고리즘 시간 복잡도 비교