티스토리 뷰

# 셸 정렬 개념 및 원리


 셸 정렬(shell sort)은 Donald L. Shell 이 제안한 방법으로 삽입 정렬이 어느 정도 정렬 되어 있는 배열에 대해서는 대단히 빠르다는 점을 이용해 만든 방법이다. 셸 정렬은 삽입 정렬의 시간 복잡도 $O(n^2)$보다 빠르다.


 삽입 정렬의 문제점은 요소들일 삽입될 때, 이웃한 위치로 한 칸씩만 이동한다는 점이다. // 제 블로그에 삽입 정렬로 검색하시면 관련 설명과 알고리즘을 확인해보실 수 있습니다. 삽입 정렬은 for 루프를 이용해 인접한 위치부터 한 칸씩 이동하며 삽입할 위치를 탐색하므로 만약 삽입할 원소가 들어갈 자리가 멀리 떨어져 있다면 한 칸씩 이동하는 설계 때문에 불필요하게 많은 반복과 비교를 해야 한다는 단점이 있습니다.


 셸 정렬에서는 요소들이 멀리 떨어진 위치로 이동할 수 있다는 장점이 있다. 이런 것이 가능한 이유는 셸 정렬이 전체의 배열(리스트)을 한 번에 정렬하지 않는다는 점 때문이다. 대신 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다.


 실제로 여러 개의 부분 리스트가 생기고 이것들을 병합하는 것이 아니라, 단순히 gap 값으로 간격을 주어 부분 리스트가 만들어진 것처럼 구현한다. 하나의 단계에서 모든 부분 리스트가 정렬이 되면 셸 정렬은 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 되풀이한다. 이러한 과정은 부분 리스트의 개수가 1이 될 때까지 되풀이된다.


 부분 리스트를 구성할 때는 주어진 리스트의 각 $k$번째 요소를 추출하여 만든다. 이 k를 우리는 간격(gap)이라 부른다. 셸 정렬에서는 각 단계별로 gap을 줄여가면서 수행 과정이 반복되므로 하나의 부분 리스트에 속하는 레코드들의 개수는 증가된다. gap이 1이 될 때까지 반복 한다.



# 셸 정렬 예시


 예를 들어 원소가 (11, 9, 7, 21, 5, 4, 23, 2, 1, 14, 16)로 구성되어 있는 크기 11의 배열이 있다고 했을 때 셸 정렬 적용하는 과정을 아래의 표와 함께 살펴보자. // 직접 표를 보며 손으로 써 보며 따라가는 것이 좋은 공부법이다.




 첫째로 먼저 gap을 설정을 해야하는데 gap은 보통 배열(리스트)의 크기를 2로 나눠 사용한다. gap은 홀수로 다루는 것이 성능에 더 좋은 영향을 끼친다는 연구 결과를 토대로 gap이 짝수라면 1을 더해서 짝수로 만들어준다. 


 배열의 크기는 11이므로 첫 gap 값은 5로 설정된다. 입력 배열의 각 5 번째 요소를 추출하여 부분 배열(리스트)을 만든다는 생각으로 표를 살펴본다. (10, 3, 16) 으로 구성된 부분 배열1, (8, 22) 로 구성된 부분 배열2, ... , (4, 15) 로 구성된 부분 배열 5 이렇게 총 5개의 부분배열이 추출된다. // 각 인덱스에 5를 더한 인덱스에 해당하는 값들로 구성되어 있음을 알 수 있다.


 추출된 부분 배열을 삽입 정렬 알고리즘으로 정렬하면 그 아래에 있는 정렬 후 부분리스트가 등장하게 된다. 그리고 이 정렬 된 부분리스트 들을 합치면 정렬 후 전체배열 항목이 등장한다. 아직 완전히는 아니지만 그래도 어느 정도 정렬이 되었음을 확인할 수 있다.


 위에서 언급했다시피 실제로 부분 리스트들을 여러 개 만들어서 하는 것이 아니라 단지 gap 값만 변화시켜 가며 삽입 정렬을 시행하는 것 뿐이다.


 셸 정렬의 첫 번째 단계가 끝나면 비슷한 방식으로 다시 부분리스트를 구성하는데 이 때도 기존의 gap 값에 2를 나눈 것을 간격으로 사용한다. 마찬가지로 짝수일 경우 홀수값으로 gap 값을 설정한 후 진행한다. // 1을 더하는 것으로 홀수를 만들어준다. 이렇게 하는 것이 성능에 더 도움이 된다고 한다.



# 셸 정렬의 구현 및 알고리즘


 외부 for문은 gap 값을 절반씩 줄이는 기능을 수행하면서 각 부분 리스트에 대하여 일정한 간격으로 떨어져 있는 요소들을 삽입 정렬하는 gap_insertion_sort 를 호출하였다. 만약 gap 값이 짝수라면 1을 더해줌으로써 홀수로 만들어주는 작업도 추가했다. gap_insertion_sort 함수는 기존의 삽입 정렬 알고리즘과 동일하다. 단지 숫자만 몇 개 바뀌었을 뿐이다. 

/*************************************************
 ** 셸 정렬과 삽입 정렬 (shell sort & insertion sort)
*************************************************/

int gap_insertion_sort(int list[], int first, int last, int gap);

// 셸 정렬 알고리즘
int shell_sort(int list[], int n)	// n = size
{
	// gap과 내부 반복을 위한 j를 변수로 선언
	int gap, j;

	// 초기 gap 값은 배열의 크기 n을 2로 나눈 값을 사용하며
	// 각 단계 별로 2를 나눠간다.
	for (gap = n/2; gap > 0; gap /= 2)
	{
		// 짝수일 경우 1을 더해주는 것이 성능에 더 도움이 된다.
		if (gap % 2 == 0)
			gap++;

		// j는 각 부분리스트의 시작인덱스 값이다.
		// j가 gap 이전까지만 가는 건 시작 인덱스 값과 gap 값만 알면
		// 배열의 끝까지 갈 수 있기 때문으로 실제 그 과정을
		// 표를 보고 그림을 그려가며 살펴보면 쉽게 알 수 있다.
		for (j = 0; j < gap; j++)
			gap_insertion_sort(list, j, n - 1, gap);
	}
}

// 시작 인덱스 first 부터 시작하는 부분리스트를 구성해 삽입 정렬을 시행한다.
int gap_insertion_sort(int list[], int first, int last, int gap)
{
	int i, j, key;

	// 삽입 정렬에서도 첫 번째 원소는 정렬을 할 필요가 없으므로
	// 그 다음 인덱스 값을 key값으로 설정해줬기 때문에 초기값은
	// first + gap이다.
	for (i = first + gap; i <= last; i += gap)
	{
		// 각 반복별로 인덱스 i값에 gap을 더해줌으로써 부분 리스트 삽입 정렬을 구현
		key = list[i];

		// 키 값 이전의 배열의 값들을 조사하면서 key값이 들어갈 위치를 찾는다.
		for (j = i - gap; j >= first && list[j] > key; j -= gap)
		{
			// 마찬가지로 각 반복별로 1을 감소시키는 것이 아닌 gap을 감소시킴으로써
			// 부분리스트의 삽입 정렬을 구현한다.
			list[j + gap] = list[j];
		}
		list[j + gap] = key;
	}
}
 

/*************************************************
 ** End Line
*************************************************/



# 셸 정렬의 시간 복잡도


 삽입 정렬에 비해 셸 정렬은 아래와 같은 장점이 있다.

  • 연속적이지 않은 부분 리스트에서 자료의 교환을 진행하여 더 큰 거리를 이동한다. 기존의 삽입 정렬에서는 한 칸씩 이동하며 비교를 하여 key 값의 자리를 찾았기 때문에 먼 거리를 이동할 경우 그만큼 반복 비교 연산이 많이 일어나는 단점이 있었다.
     더 큰 거리를 이동함으로써 교환되는 요소들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 더 높아진다. 최종 자리를 더 빨리 찾아감으로써 연산의 횟수를 줄이는 데 기여할 수 있다.

  • 삽입 정렬은 어느 정도 정렬이 된 배열에서 더 빠르게 작동한다는 것을 우리는 알고 있다. 이 점을 토대로 우리는 한 번에 정렬하는 것이 아니라 부분 리스트를 구성해 조금씩 정렬된 상태를 만들어가는 것이므로 삽입 정렬에 비해 속도가 점점 더 빠르게 수행된다.

 실험적인 연구를 통하여 증명된 셸 정렬의 시간 복잡도는 대략 최악의 경우에는 $O(n^2)$이지만 평균적인 경우에는 $O(n^{1.5})$로 나타난다.



댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday