[Sorting 05] Insert Sort의 개념 및 구현

들어가며

---

날이 엄청 춥다. 드디어 겨울이 오나보다.
오늘은 개념은 쉽지만 비효율적인 알고리즘 중에 하나인 'Insert Sort'에 대해 알아보자.

개념 및 특징

---

• 이미 정렬된 리스트를 앞에서 부터 값을 비교하여 자신의 위치를 찾아 삽입함으로써 정렬하는 알고리즘이다.
• in-place 알고리즘이다.
• 시간 복잡도: O(N2)
• 선택정렬이나 거품정렬에 비해서는 빠르다.*

알고리즘

---

1. 앞에서부터 차례대로 이미 정렬된 리스트와 비교하여 자신의 위치를 찾아 삽입한다.
2. 리스트의 모든 원소에 대해 위와 1과 같은 과정을 반복한다.

소스코드(C++)

---

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

using namespace std;

typedef vector<int>::iterator IT;

void insertSort(IT bit, IT eit)
{
	IT i, j, k;
	for(i=bit+1; i!=eit; i++) {
		for(j=bit; j<i && !(*i <= *j); ++j)
			;
		if(j<i) {
			int tmp = *i;
			for(k=i-1; k>=j; --k, --i) 
				*i = *k;
			*j = tmp;	
		}	
	}
}

int main(void)
{
	int arr[] = {8, 7, 6, 5, 4, 3, 2, 1};
	vector<int> vc(arr, arr+sizeof(arr)/sizeof(arr[0]));
	
	copy(vc.begin(), vc.end(), ostream_iterator<int>(cout," "));
	cout << endl;
	
	insertSort(vc.begin(), vc.end());
	
	copy(vc.begin(), vc.end(), ostream_iterator<int>(cout," "));
	cout << endl;
	
	return 0;
}