삽입 정렬..이란 말이죠...

삽입 정렬(Insertion Sorting)

정리되지 않은 리스트(list)의 데이터 하나를 정렬 순서에 맞게 삽입하는 방법이며

맨 처음 한 개의 데이터가 정렬되어 있는 것으로 간주하여 수행된다.

 

손에 이미 정렬된 카드를 들고, 새 카드를 적절한 위치에 삽입하는 카드 놀이와 같다.

 

특징

이 알고리즘은 i번째 데이터 A[i]를 이미 정렬된 배열 A[1], A[2], ... , A[i-1]의 알맞은 위치를 찾아 '삽입'하는 방식으로 정렬을 수행한다. (하나씩 삽입하며 정렬)

즉, 여기서 앞의 i-1번째 데이터는 이미 정렬된 상태이다.

 

이때 올바른 위치를 찾기 위해 수행되는 연산은 A[1], A[2], ... , A[i-1]들을 A[i]와 비교하는 것이다.

비교는 A[1]부터 시작하는 경우와 A[i-1]부터 시작하는 경우로 나뉘어진다.

(우린 A[i-1]부터 비교해보자)

이런 식으로 삽입 과정을 계속하고 나면 배열 A[1], A[2], ... , A[i-1]은 정렬된 리스트가 된다. (정렬 끝!->취향껏 데이터 쓰면 됨)

 

삽입 정렬 알고리즘은 다음과 같으며 2부터 n까지의 모든 i에 대하여 A[i]는 A[1]에서 A[i-1] 내의 적절한 위치에 삽입된다.

(위 내용이 코드 쓸 때 흐름을 이해하기 좋다)

 

// 원소 이동: temp = A[i], A[j] = temp
// 원소 비교(주요 연산): A[j-1] > temp

void insertion(int A[], int n)
{
	int i, j;
    int temp;
    
    for(int = 1; i <= n; i++)
    {
    	temp = A[i];
        j = i;
        
        while(j > 0 && A[j-1] > temp)
        {
        	A[j] = A[j-1];
            j--;
        }
        A[j] = temp;
    }
}

 

n을 전체 데이터 수라고 할 때, 삽입 정렬 알고리즘은 수행 시간이 O(n^2)이며, 여분의 메모리가 일정한 크기 만큼만 요구되기 때문에 적절한 알고리즘이다.

따라서 정렬을 위해 기본적으로 키의 비교가 기본 연산이 되는 경우의 알고리즘들은 성능 차이가 내측 루프의 길이나 입력의 특수성에 의해 의존한다.

 

 

 

원소 비교 횟수

삽입 정렬의 연산 수행 시간은 주요 연산의 수행 시간으로 알 수 있다.

삽입 정렬의 주요 연산은 원소 비교 연산이므로, 연산 비교 회수를 분석해 수행시간을 O(n)으로 나타내보자

최악의 경우이던, 최상의 경우이던 원소 비교는 이뤄진다.

다만 그게 1번으로 끝나냐..(n-1)번까지 비교해야 끝나냐에 따라 달렸지만은...(while문에서 뺑뺑이 도는 시점)

 

최악의 경우

입력 데이터 (n-1)개가 역으로 정렬되어 있는 경우

1+2+...+(n-1) = n(n-1)/2 = O(n^2)

증명

최상의 경우

입력 데이터가 정렬하고자 하는 순서대로 배열되어 있는 경우

전체 비교 횟수: (n-1)번

수행 복잡도: O(n)

n-1 = O(n)

 

평균의 경우

O((m+1)n)

- m: 순서에 벗어난 데이터 개수 (m=0일 경우, 정렬된 데이터를 의미하므로 최상의 경우라 할 수 있다)

O(n^2)

- 최악의 경우 알고리즘 복잡도는 O(n^2)이 되며 평균의 경우의 알고리즘 복잡도 역시 O(n^2)이 된다

O(n^2) or O((m+1)n)

 

 

원소 비교 횟수 vs 원소 이동 횟수 분석

두 연산 모두 O(n^2)의 작업량을 가진다

 

장단점

순서가 틀린 자료(m)가 적을 때 유리

20~25개 이하 정렬에 효과적

이동량 증가(앞서 이동한 데이터들이 또 이동하는 경우 o)