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

 원리 

1. 0번부터 n번 인덱스의 데이터를 차례대로 선택하자

2. 선택한 인덱스부터 0까지 인접한 인덱스를 비교하자

3. 만약 인덱스가 낮은 원소가 더 크다면 교환하고 아니라면 탈출한다. (오름차순기준)

 

 [ 70, 55, 30, 47, 66 ]

 

(70) 55 30 47 66 --> "70" 55 30 47 66

70 (55) 30 47 66 --> "55" 70 30 47 66

55 70 (30) 47 66 --> "30" 55 70 47 66

30 55 70 (47) 66 --> 30 "47" 55 70 66

30 47 55 70 (66) --> 30 47 55 "66" 70

 

정렬 후 : [ 30 47 55 66 70 ]

 

 구현 

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

 

삽입 정렬은 선택된 원소(여기선 i+1)가 i+1보다 작은 인덱스를 순회하면서, 도착한 인덱스의 데이터가 선택된 원소보다 크다면 그 인덱스의 데이터와 인덱스 + 1 데이터와 스왑하고 있습니다.

 

i가 0일때 arr[0] < arr[1] 로 정렬되고 다음 i가 1일 때 arr[0] < arr[1] 즉, i번째보다 작은 인덱스의 원소는 i번째 인덱스의 원소보다 작다는 것이 자명하므로 위 알고리즘이 성립합니다.

 

사실 이 내용은 위 코드 내용을 그대로 옮겨 쓴것인데 만약 위 내용이 받아들여지지 않는다면 직접 수를 나열해서 정렬을 해본다면 몸소 느낄 수 있습니다.

 

 시간복잡도 

내림차순 기준으로 정렬하려 할때 최악의 경우 배열이 오름차순 정렬되어있다면, 매번 i번째부터 0번째까지 스왑이 되므로  O(n^2)의 시간복잡도를 가지게 됩니다.

 

반대로, 모든 원소가 내림차순으로 정렬되어있다면 두번째 포문에서 바로 break로 탈출하기 때문에 O(n)의 시간복잡도를 가지게 됩니다.

 

 정리 

이름	BEST	AVG	WORST	RUN TIME(정수 60,000)
버블 정렬	n^2	n^2	n^2	확인
선택 정렬	n^2	n^2	n^2	확인
삽입 정렬	n	n^2	n^2	사진 참고

 

삽입 정렬 런타임 (랜덤 정수 60,000개)

랜덤 정수 60,000개 정렬 결과 약 9s ~ 10s 사이의 결과가 나왔습니다.

 

추가적으로 정수 데이터 6만개를 정렬시킨후 삽입정렬한 결과는 아래와 같습니다.

삽입 정렬 런타임 (미리 정렬된 정수 데이터 60,000개)

약 0ms로 측정되었습니다.

 

실행 환경 :

- windows 10 WSL2 - ubuntu 18.04

- gcc 7.4.0

- cpu : i3

 참조 

위키백과 - 삽입 정렬

삽입 정렬 - 위키백과, 우리 모두의 백과사전