Sorting I - Insertion Sort

정렬된 데이터는 정렬되지 않은 데이터에 비해 여러가지 장점이 있다.

탐색도 정렬되지 않은 데이터는 O(n), 정렬된 데이터는 O(logn)으로 정렬된 데이터가 훨씬 빠르다.

이 외에도 여러 장점 때문에 데이터를 정렬할 필요가 있다.

정렬 방식에 어떤 것들이 있고, 복잡도는 어떤지 하나씩 알아보자.

 

Insertion Sort

삽입 정렬은 element 하나씩 적절한 위치로 삽입하며 정렬하는 알고리즘이다.

 

Example

위와 같은 정수 배열을 삽입 정렬을 통해 오름차순으로 정렬해보자.

 

 

먼저 첫번째 element는 정렬이 되어있다고 가정한다.

 

 

다음으로 정렬되지 않은 element, 2를 올바른 위치에 삽입해준다.

배열의 맨 앞에 오거나(index=0) 앞의 element보다 key 값이 클 때까지(E[cur-1]<E[cur]) 이동하면 된다.

위의 경우 5보다 2가 작으므로 5의 앞으로 이동하고, index가 0이므로 종료하면 두번째 element까지 정렬이 완료된다.

 

 

세번째 element도 마찬가지로 이동해준다.

5보다는 크니 앞으로 이동하고 2보다는 작으니 해당 위치에서 멈추면 세번째 element까지 정렬 완료.

 

 

네번째 element(6)는 앞의 element(5)보다 크기 때문에 현재 위치가 올바른 위치이다. 네번째까지 정렬 완료.

 

 

다섯번째 element는 앞의 모든 element보다 작아 맨 앞으로 이동하여 정렬 완료.

 

 

마지막 element까지 올바른 위치로 이동시켜주면 모든 element가 정렬이 완료된다.

 

Complexity

삽입 정렬의 worst case는 배열이 역순으로 정렬되어 있을 때이다.

2번째 element는 1번, 3번째 element는 2번, ... , n번째 element는 n-1번의 이동이 필요하다.

따라서 1 + 2 + 3 + ... + n-1 = n(n-1)/2 이므로, 점근 표기법으로 O(n^2)의 시간복잡도를 갖는다.

 

Source Code (C++)

void insertionSearch(int* E, int n) {
	for (int i = 1; i < n; i++) {
		while (E[i - 1] > E[i] && i > 0) {
			swap(E[i - 1], E[i]);
			i--;
		}
	}
}

코드는 앞서 설명한대로 두번째 element부터 하나씩 순서에 맞는 위치까지 이동하도록 구현하면 된다.