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

셸 정렬이란?

이전에 포스팅 했던 삽입 정렬은 시간 복잡도가 $O(n^2)$로 정렬 알고리즘 중에서는 느린 축에 속하는 정렬 방식이었습니다. 하지만 삽입 정렬은 어느 정도 배열이 정렬이 된 상태라면 시간 복잡도를 줄일 수 있습니다. 이에 착안해 도널드 셸(Donald L.Shell)이라는 창시자가 본인의 이름을 따 셸 정렬이라고 부르게 됩니다.

 

쉘 정렬은 정렬해야 할 리스트를 일정한 간격에 따라 나눕니다. 그렇게 여러 개로 나누어진 부분 리스트를 만들어 각 부분 리스트를 삽입 정렬을 이용해 정렬하는 방식입니다.

 

 

셸 정렬 구현

셸 정렬의 핵심은 간격입니다.

 

셸 정렬이 구현되어 있는 함수에서는 처음 간격이 (배열 혹은 리스트 크기 / 2)로 시작했다가 1이 될 때까지 정렬을 반복합니다.

간격이 줄어들면서 점차 정렬이 되기 시작하고, 기존의 데이터들이 어느 정도 정렬되었기 때문에 삽입 정렬만 사용했을 때보다 시간이 덜 소모되는 것입니다.

 

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

inc_insertion_sort(int list[], int first, int last, int. gap) {
	int key;
	for(int i = first + gap; i <= last; i += gap) {
		key = list[i];
		for(j = i - gap; j >= first && key < list[j]; j -= gap) {
			list[j + gap] - list[j];
		}
		list[j + gap] = key;
	}
}

void shell_sort(int list[], int n) {
	int gap;
	for(gap = n / 2; gap > 0; gap /= 2) {
		if((gap % 2 ) == 0) gap++;
		for(int i = 0; i < gap; i++) {
			inc_insertion_sort(list, i, n - 1, gap);
		}
	}
}

 

셸 정렬의 시간 복잡도

셸 정렬은 최악의 경우에는 $O(n^2)$에, 평균적으로 $O(n \space log \space n)$에 수행되는 것으로 알려져 있습니다.

 

 

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

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

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

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

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

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

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