[Algorithm] 정렬 - 삽입 정렬 (Insertion Sort)

삽입 정렬(Insertion Sort)이란?

이름 그대로,

원소가 들어갈 적당한 자리를 찾아, 삽입하여 정렬하는 방식이다.

 

예)

 

1)  배열의 두 번째 값부터 시작한다.

    arr[1]은 key값으로 따로 저장해놓는다.

 

2)  key값과, 이전 값인 arr[0]값을 비교한다.

 

3)  이전 값(arr[0])이 key값보다 크므로, 값을 뒤로 한칸 이동시킨다.

    (arr[0]에 실제로 값이 없어지는 것은 아니지만, 이해를 위해 지웠습니다.)

 

4)  더 이상 이전으로 이동할 수 없으므로, 비교를 끝내고 저장해놨던 key값을 arr[0]에 설정한다.

 

5)  다음 값을 key값으로 설정한다.

 

6)  key값과, 이전 값을 비교한다.

    key값이 더 크므로, 다음으로 넘어간다.

 

7)  다음 값을 key값으로 설정한다.

 

8)  key값과, 이전 값을 비교한다.

    key값이 더 크므로, 다음으로 넘어간다.

 

9)  다음 값을 key값으로 설정한다.

 

10)  key값과, 이전 값을 비교한다.

 

11)  arr[3]값이 key값보다 크므로, 값을 한칸 뒤로 이동시킨다.

 

12)  하나 더 이전 값인 arr[2]와 key값을 비교한다.

 

13)  arr[2]값이 key값보다 크므로, 값을 한칸 뒤로 이동시킨다.

 

14)  하나 더 이전 값인 arr[1]과 key값을 비교한다.

 

15)  arr[1]값이 key값보다 크므로, 값을 한칸 뒤로 이동시킨다.

 

16)  하나 더 이전 값인 arr[0]과 key값을 비교한다.

 

17)  arr[0]값보다 key값이 더 크므로, 비교를 끝내고 arr[1]에 저장해놨던 key값을 설정한다.

 

18)  arr[4]까지 모두 돌았으므로, 정렬 작업을 끝낸다.

 

 

소스코드

#include <iostream>

using namespace std;

void insertionSort(int* arr, int len);

int main() {
	int N;
	cin >> N;

	int* arr = new int[N];
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	insertionSort(arr, N);

	for (int i = 0; i < N; i++) {
		cout << arr[i] << endl;
	}

	delete[] arr;

	return 0;
}

void insertionSort(int* arr, int len) {
	for (int i = 1; i < len; i++) {
		int key = arr[i];

		int prev = i - 1;
		while (prev >= 0) {
			if (key < arr[prev]) {
				arr[prev + 1] = arr[prev];
				prev--;
			}
			else {
				break;
			}
		}

		if (prev + 1 != i) arr[prev + 1] = key;
	}
}

 

시간복잡도

평균의 경우 : O(n²)

 

최선의 경우 : O(n)

배열에 값이 이미 정렬되어 있는 경우, 하나 앞의 값하고만 비교하면 된다.

 

최악의 경우 : O(n²)

배열에 값이 역순으로 정렬되어 있는 경우, 데이터 총 개수가 n이라고 하면, 비교 횟수는 아래와 같다.

1 + 2 + ... + (n-2) + (n-1)

= n(n-1) / 2

= O(n²)