01. 요약

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

02. 원리 (작동 방식)

  • 동작 과정
    1. 먼저 정렬해야 할 리스트를 일정한 기준에 따라서 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만든다.
    2. 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다.
    3. 모든 부분 리스트가 정렬되면 쉘 정렬은 다시 전체 리스트를 더 작은 개수의 부분 리스트로 만든 후에 알고리즘을 되풀이한다.
    4. 위의 과정을 부분 리스트의 개수가 1이 될 때까지 되풀이 한다.

shellsort 동작 과정 한 단계

  • 구현 과정
    1. ‘간격(gap)’을 나타내는 k값을 정하고, 정렬해야 할 리스트의 각 k번째 요소를 추출해서 부분리스트를 만든다.
      • 간격의 초깃값 : (정렬할 값의 개수)/2
      • 간격의 값 k는 홀수인 게 좋다고 분석되었다. 짝수일 경우 1을 더한다.
      • 생성된 부분 리스트의 개수는 gap과 같다.
    2. 각 부분 리스트를 삽입 정렬을 이용해 정렬한다.
    3. 각 스텝마다 간격 k를 줄여가므로, 수행과정이 반복될 때마다 하나의 부분리스트에 속하는 레크드들의 개수는 증가한다.
    4. 간격 k의 값이 1일 될때까지 반복한다.

shellsort 동작 과정 전체

  • 이해 돕기
    1. 처음 간격 k = 5 (10/2), 다섯 번째 요소를 추출해 부분리스트를 만든다.
      • 첫 번째 부분 리스트 : [10, 3, 16]
      • 두 번째 부분 리스트 : [8, 22]
      • … (이런 식으로 진행)
    2. 각 부분 리스트에 대하여 삽입 정렬
    3. 다음 간격 k = 3(5/2 + 1)로 한다. 짝수일 경우 +1을 해서 홀수로
    4. 이런 방식으로 진행한다.

03. 순서도 (알고리즘)

// 기존의 삽입 정렬 알고리즘과 거의 동일하나, gap 단위로 삽입 정렬하는 알고리즘
const ShellInsertionSort = (array, first, gap) => {
	let i;
	let j;
	let key;
	let last = array.length - 1;

	// 삽입 정렬은 원래 n + 1부터 시작
	for (i = first + gap; i <= last; i += gap) {
		key = array[i];

		// 삽입할 위치를 찾기 위해서 선택한 key의 앞에서부터 비교해가면서 한칸씩 오른쪽으로 민다.
		for (j = i - gap; j >= first && array[j] > key; j -= gap) {
			array[j + gap] = array[j];
		}

		// 삽입할 위치를 찾았으니 삽입한다.
		array[j + gap] = key;
	}
};

const ShellSort = (array) => {
	let i;
	let gap;
	let length = array.length;

	// gap의 초기값은 보통 반의 크기로 한다.
	for (gap = parseInt(length / 2); gap > 0; gap = parseInt(gap / 2)) {
		// gap은 짝수보다 홀수가 더 좋은 것으로 분석되었다. 짝수일 경우 홀수로 만들어준다.
		if (gap % 2 === 0) gap++;

		// 각 부분리스트에 대해서 삽입 정렬을 수행한다
		// index를 이용해 처리하기 때문에 추가적인 배열 공간은 필요 없다.
		for (i = 0; i < gap; i++) {
			ShellInsertionSort(array, i, gap); // 6.
		}
	}
};

const array = [3, 2, 6, 1, 5, 4];
ShellSort(array);
console.log(array);

04. 특징

  • 장점 (삽입 정렬에 비하여)
    • 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동한다. 반면 삽입 정렬에서는 한 번에 한 칸씩만 이동된다. 따라서 교환되는 아이템들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 높아진다.
    • 부분 리스트는 어느 정도 정렬이 된 상태이기 때문에 부분 리스트의 개수가 1이 되게 되면, 쉘 정렬은 기본적으로 삽입 정렬을 수행하는 것이지만 빠르게 수행된다. (이는 삽입정렬이 거의 정렬된 리스트에 대해서는 빠르게 수행되기 때문이다.)
  • 단점
    • 생략

05. 복잡도

  • 시간복잡도
    • 증명은 되어있지 않고, 실험적인 연구를 통한 자료이다.
    • 최악의 경우 O(n^2)
    • 평균의 경우 O(n^1.5)
    • 최선의 경우 O(n)
  • 쉘 정렬은 나누는 간격의 값에 따라 시간에 크게 영향을 받는다고 한다. 이 나누는 간격이 최악의 경우 O(n^2)의 시간 복잡도를 갖는다. 그렇다면 이게 삽입정렬 보다 더 빠른게 맞을까?
  • 쉘 정렬 자체는 그리 빠르지는 않다. 다만, 삽입 정렬보다 평균적인 경우 보다 더 빠르다는 것이다.
  • 삽입 정렬은 최선의 경우 O(n), 평균의 경우 O(n^2), 최악의 경우 O(n^2)이다.
  • 쉘 정렬은 평균의 경우 O(n^1.5)로 대체적으로 빠르다고 보면 될 것 같다.

06. 참고