[자료구조] 삽입 정렬 (insertion sort)

삽입 정렬이란?

정렬이 되어 있는 왼쪽 리스트와 정렬이 되어 있지 않은 오른쪽 리스트로 나누었다고 가정해봅시다.

 

배열의 첫 원소부터 차례대로 앞에 이미 정렬되어 있는 왼쪽 리스트와 비교하며 어느 자리에 들어갈 지 위치를 판단한 후, 적절한 위치에 삽입하는 정렬 방식입니다.

 

 

삽입 정렬 구현

삽입 정렬의 핵심 또한 왼쪽 리스트와 오른쪽 리스트를 분리하는 것입니다.

 

각자 아래 목적에 맞게 분리되어야 하므로 반복문을 통해 숫자가 담겨있는 배열이나 리스트에 제대로 접근해야 합니다.

• 왼쪽 리스트: 오름차순 (혹은 내림차순) 으로 정렬이 되어있는 상태여야 함.
• 오른쪽 리스트: 정렬 관계는 상관 없지만, 왼쪽 리스트에 어느 부분에 삽입되어야 할 지 정확히 계산해야 합니다.

 

코드로 구현하면 아래와 같습니다.

void insertion_sort(int list[], int n) {
	int i, j, k;
	for(i = 1; i < n; i++) {
		key = list[i];
		for(j = i - 1; j >= 0 && list[j] > key; j--) {
			list[j + 1] = list[j];
		}
		list[j + 1] = key;
	}
}

 

삽입 정렬의 시간 복잡도

삽입 정렬 또한 반복문이 이중으로 들어가있는 것을 볼 수 있기 때문에 $O(n^2)$입니다.

 

 

[자료구조] 선택 정렬 (selection sort)

[자료구조] 버블 정렬 (bubble sort)

[자료구조] 셸 정렬 (shell sort)

[자료구조] 합병 정렬 (merge sort)

[자료구조] 퀵 정렬 (quick sort)

[자료구조] 힙 정렬 (heap sort)

[자료구조] 기수 정렬 (radix sort)