셸 정렬에 관해

2020-04-09

1. 셸 정렬의 원리 (작동 방식)

  • Donald L. Shell이라는 사람이 제안한 방법으로, 삽입정렬을 보완한 알고리즘이다.
  • 삽입 정렬이 어느 정도 정렬된 배열에 대해서 대단히 빠른 것에 착안했다.
  • 삽입 정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동한다는 점
  • 즉, 만약 삽입되어야 할 위치가현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있다. 셸 정렬에서는 요소들이 멀리 떨어진 위치로도 이동할 수 있다.
  • 삽입 정렬과 다르게 셸 정렬은 전체 리스트를 한 번에 정렬하지 않는다.

1.5 구현 방법

  • 간단하게 설명해서 전체 리스트에서 일정한 기준에 따라 몇 개의 부분 리스트로 나누고 각 부분 리스트를 삽입 정렬을 이용해 정렬한다. 위 과정을 부분 리스트의 개수가 1개가 될 때까지 반복한다. 실제로 부분 리스트들이 만들어지는 것은 아니고 일정한 간격으로 삽입 정렬을 수행하는 것뿐이니 추가적인 공간은 필요 없다.
  • 구현 순서
  • 정렬해야 할 리스트의 각 k번째 요소를 추출해서 부분 리스트를 만든다. 이 때, k를 ‘간격(gap)’이라고 한다.

    간격의 초기값 : (정렬할 값의 수) / 2 생성된 부분 리스트의 개수는 gap이 된다.

  • 각 회전마다 간격 k를 절반으로 줄인다. 각 회전마다 하나의 부분 리스트에 속한 값들의 개수가 증가한다. 이때 간격이 짝수일시 +1을 해서 홀수로 만드는 것이 좋은 것으로 분석되었다.
  • 간격 k가 1이 될 때까지 반복한다.

2. 구현 또는 순서도 (자바)

	static void inc_insertion_sort(int arr[], int first, int last, int gap) {
		for(int i=first+gap; i<=last; i=i+gap) {
			int insertValue = arr[i];
			int insertIndex = i;
			for(int j=i-gap; j>=first && arr[j] > insertValue; j=j-gap) {
				arr[j+gap] = arr[j];
				insertIndex = j;
			}
			arr[insertIndex] = insertValue;
		}
	}
	
	static void shell_sort(int arr[], int n) {
		for(int gap = n/2; gap > 0; gap = gap/2) {
			if( gap%2 == 0 ) {
				gap++;
			}
			for(int i=0; i<gap; i++) {
				inc_insertion_sort(arr, i, n-1, gap);
			}
		}
	}

3. 셸 정렬의 특징

  • 삽입 정렬에 비하여 셸 정렬은 2가지 장점이 있다.

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

  2. 부분 리스트는 어느 정도 정렬이 된 상태이기 때문에 부분 리스트의 개수가 1이 되게 되면
    셸 정렬은 기본적으로 삽입 정렬을 수행하는 것이지만 삽입 정렬보다 더욱 빠르게 수행된다.

4. 셸 정렬의 시간 복잡도 (분석)

  • 실험적인 연구를 통해 셸 정렬의 시간복잡도는 최악의 경우 O(n^2)이지만 평균적인 경우에는 O(n^1.5)로 나타난다.

출처

  1. C언어로 쉽게 풀어쓴 자료구조 (천인국, 공용해, 하상호 지음)

  2. https://gmlwjd9405.github.io/2017/10/01/basic-concepts-of-development-algorithm.html