EunSung.log

쉘 정렬

5 min read

개요

쉘 정렬Shell Sort은 삽입 정렬을 보완한 정렬 알고리즘이다. 1959년 Donald L. Shell에 의해 제안되었으며, 이 사람의 이름을 따서 쉘 정렬이라 불린다.
한 마디로 요약하자면, 간격을 두고 삽입 정렬을 수행하며 점차 간격을 줄여가는 정렬 알고리즘이다.

설명

쉘 정렬은 삽입 정렬의 다음 특징을 이용, 보완한 정렬 알고리즘이다.

  • 어느 정도 정렬된 상태일 때 효율적이다.
  • 각 항목이 한 번에 한 자리씩만 이동하기 때문에 비효율적이다.

쉘 정렬은 리스트 전체를 한 번에 정렬하지 않고, 하나의 리스트를 여러 개의 부분 리스트로 나누어 각 부분 리스트를 삽입 정렬을 이용해 정렬한다.

이 부분 리스트는 주어진 리스트의 각 번째 원소를 추출해 만든다. 이 를 간격(gap)이라 칭하며, 쉘 정렬은 이 가 1이 될 때까지 반복한다.

이렇게 하면 초기에 멀리 떨어진 원소들을 정렬하기 때문에, 각 항목이 한 번에 한 자리씩만 이동한다는 삽입 정렬의 단점이 해결된다. 뿐만 아니라 간격이 1이 되었을 때(전체 리스트를 정렬할 때)는 리스트가 어느 정도 정렬된 상태이므로, 효율적인 정렬이 가능하다.

동작

  1. 리스트의 각 k번째 요소를 추출해 부분 리스트를 만든다.
  2. 각 부분 리스트에 대해 삽입 정렬을 수행한다.
  3. k의 크기를 줄인다.
  4. k가 1이 될 때까지 위 과정을 반복한다.
    • 단, k = 1일 때도 삽입 정렬을 수행한 뒤 종료.

시간 복잡도

쉘 정렬은 구현은 간단하지만, 시간 복잡도 분석은 어렵다. 그 이유는 쉘 정렬의 핵심인 간격 의 크기를 줄이는 방식(gap sequence)에 따라 시간 복잡도가 달라지기 때문이다. 영어 위키백과의 쉘 정렬 문서에는 여러 gap sequence가 소개되어 있는데, 여기서는 Shell이 제안한 방법에 대해서만 정리해둔다.

  • Shell이 제안한 Gap sequence = (n/2, n/4, … , 1)
    • 최선의 경우:
    • 최악의 경우:
    • 평균적인 경우:

추가로 작성하자면, Sedgewick이 제안한 gap sequence를 사용할 경우 최악의 경우 시간복잡도가 이 나온다.

특징

구현

public static class ShellSort {
	public static void sort(int[] array) {
		int n = array.length;
		for (int gap = n / 2; gap > 0; gap /= 2) {			
			for (int i = gap; i < n; i++) {
				int temp = array[i];
				int j = i;
				
				while (j >= gap && arr[j - gap] > temp) {
					array[j] = array[j - gap];
					j -= gap;
				}
 
				array[j] = temp;
			}
		}
	}
}

참고

『C언어로 쉽게 풀어쓴 자료구조』(개정 3판)에서는 간격이 짝수일 때는 1을 더해 홀수로 만들어 사용한다.

만약 간격이 짝수이면 1을 더하는 것이 좋은 것으로 분석되었다. 따라서 소스에서도 짝수인 경우 간격에 1을 더해주었다. - p.460

참고문헌

백링크