[알고리즘] 셸 정렬(shell sort) 란 - travelbeeee

안녕하세요, 여행벌입니다.

오늘은 셸정렬(shell sort)에 대해서 포스팅해보겠습니다.

---

셸 정렬의 원리

 셸 정렬(shell sort)은 Donald L. Shell 이라는 사람이 제안한 방법으로 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠르게 정렬한다는 사실에 착안한 방법입니다.

 

 삽입 정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동하기 때문에 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야 합니다. 셸 정렬에서는 바로 이웃한 위치로만 이동하는 게 아니라 멀리 떨어진 위치로도 이동을 할 수 있습니다. 

 

 삽입 정렬과는 다르게 셸 정렬은 전체의 리스트를 한 번에 정렬하지 않습니다. 대신에 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬합니다. 모든 부분 리스트가 정렬되면 셸 정렬은 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 이 과정을 되풀이합니다.

 

 부분 리스트를 구성할 때는 주어진 리스트의 각 K 번째 요소를 추출하여 만들고, 이 K를 간격(gap)이라고 합니다.

이 K를 줄여가며 수행 과정을 반복합니다.

 

 셸 정렬은 삽입 정렬을 보완할 정렬로 삽입 정렬에 비해 2가지 장점이 있습니다.

 

 1. 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동하므로 교환되는 요소들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 높아진다.

 2. 부분 리스트는 어느 정도 정렬이 된 상태이기 때문에 부분 리스트의 개수가 1이 되었을 때, 삽입 정렬이 훨씬 빠르게 수행된다.

---

셸 정렬 예시

( 10 2 5 4 1 6 9 8 7 3 ) 리스트를 셸 정렬을 이용해서 정렬해보겠습니다.

처음의 K(gap) = N / 2 = 5 입니다.

K가 5이므로 5칸 떨어진 요소들과 부분 리스트를 이루게 됩니다.

10과 6이 같은 부분 리스트이므로 6과 10으로 삽입 정렬을 통해 정렬됩니다.

2와 9 / 5와 8 / 4 와 7 / 1 과 3도 각각 같은 부분 리스트에 속하지만 정렬이 되어있으므로 삽입 정렬을 수행하지 않습니다.

 

이제 K(gap)을 반으로 줄입니다.

K가 2이므로 2칸 떨어진 요소들과 부분 리스트를 이루게 됩니다.

6 - 5 - 1 - 9 - 7 / 2 - 4 - 10 - 8 - 3 이 각각 부분 리스트를 이루게 되고,

각각 삽입 정렬을 통해 정렬하게 됩니다.

 

또, K(gap)을 반으로 줄입니다.

K가 1이므로 1칸 떨어진 요소, 즉 전체 리스트에 대해서 삽입 정렬을 수행합니다.

모든 과정을 표로 표현하면 다음과 같습니다.

---

셸 정렬 코드

 간격은 처음에는 n / 2 로 하고 각 패스마다 간격을 절반으로 줄여 간격이 1이 될 때까지 셸 정렬을 수행하면 된다.

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

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

---

셸 정렬 복잡도

 셸 정렬의 동작 원리는 삽입 정렬을 이용해서 정렬합니다. 따라서, 최악의 경우 , 최선의 경우가 삽입 정렬과 동일한 복잡도를 가집니다. 하지만 실험적인 연구를 통해서 셸 정렬의 평균 시간 복잡도는 삽입 정렬과 다르게 n^(1.5) 를 따른다고 합니다.

 

---

셸 정렬 안정성

 셸 정렬은 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있는 불안정 정렬에 속합니다.

 [ 5-1 5-2 3 2 1 ] 를 셸 정렬로 정렬해보겠습니다.

[ 5-1 5-2 3 2 1] → [ 1 2 3 5-2 5-1 ]

 위와 같이 셸 정렬은 같은 값이 있는 경우에 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있습니다.

---

이상으로 셸 정렬 포스팅을 마치겠습니다.