[자료구조(C언어)] 정렬 2 - 삽입 정렬 (insert sort)

※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다.

---

삽입 정렬 (insert sort)

하나의 배열에 데이터들이 이미 정렬되어있을 때, 정렬을 유지하면서 새로운 데이터를 삽입하는 알고리즘이다.

새로운 데이터를 정렬된 배열의 앞에 있는 데이터부터 차례대로 비교하면서 자신의 위치를 찾아 삽입한다.

이러한 삽입 연산을 반복적으로 수행함으로써 데이터들을 정렬한다.

 

오름차순 삽입 정렬 코드 

void insertion_sort(int n, int data[]) {
	for (int i=1; i<n; i++) {
		int tmp = data[i];
		/* i-1 ~ 0까지 while문을 돌며 비교한다 */
		int j = i-1;
		while (j>=0 && data[j]>tmp) {
			/* tmp보다 큰 값들을 뒤로 한 칸씩 옮긴다. */
			data[j+1] = data[j];
			j-;
		}
		/* tmp보다 작은 값을 발견하면 그 바로 다음 자리에 tmp를 삽입한다 */
		data[j+1] = tmp;
	}
}

배열의 두번째 원소(1)부터 시작해 마지막 원소(n-1)까지 반복문을 돈다.

해당 원소를 앞에 있는 원소들(=정렬된 상태)과 비교해

적절한 위치에 삽입한다.

이렇게 data[0] ~ data[i-1] 중에 제자리를 찾아 data[i]를 삽입하는 일을 반복한다.

 

삽입정렬의 시간복잡도는 ?

최악의 경우는 데이터가 반대로 정렬되어있는 경우(내림차순으로 정렬되어있는 데이터를 오름차순으로 정렬하려고 할 때 등)이다.

이 경우 시간복잡도는 n(n-1)/2 ⇒ O(n^2)이다.

평균적으로는 절반 정도의 시간이 걸릴 것이다.

 

삽입 정렬은 버블 정렬보다 많이 쓰이는 정렬 알고리즘이다.

일반적인 경우에는 삽입 정렬이 버블 정렬보다 대략 두 배 정도 빠르기 때문이다.

 

 

그 외의 정렬 알고리즘

퀵 소트(quicksort) 알고리즘

시간복잡도 측면에서 조금 특이한 알고리즘이다.

최악의 경우에는 O(n^2)이지만, 평균 시간복잡도는 O(nlog②n)로

최악의 경우와 일반적인 경우에 효율성에 차이가 매우 크다.

최악의 경우를 제외하고 일반적으로는 나쁘지 않은 효율성을 가진 알고리즘이라고 볼 수 있다.

라이브러리 형태로도 많이 제공되므로 대부분의 경우에는 퀵 소트 알고리즘이 쓰인다.

 

합병정렬(merge sort), 힙 정렬(heap sort) 알고리즘

최악의 경우 O(nlog2n)의 시간복잡도를 가지는 정렬 알고리즘이다.

구현이 어렵지만 효율적이다.

 

+) 만약 데이터가 배열이 아닌 연결리스트에 저장되어 있다면?

어떤 경우에도 O(n^2)의 시간복잡도를 벗어나기 힘들다.

주로 삽입 정렬 알고리즘을 많이 사용한다.