셸 정렬 (Shell Sort)

[65, 73, 67, 98, 75, 80, 87, 30, 61, 45, 4, 36, 52, 5, 23, 68, 71, 70, 61, 21, 29, 73, 36, 90, 13,  97, 14, 71, 1, 51, 49, 3, 15, 64, 51, 87, 80, 8, 73, 84, 21, 93, 46, 87, 49, 41, 77, 40, 73, 96]

셸 정렬이란?

삽입정렬을 보완한 정렬

 

시간복잡도

	시간 복잡도	시간 복잡도
최악	O(n^2) (worst known worst case gap sequence)	O(n log^2 n) (best known worst case gap sequence)
평균	depends on gap sequence
최상	O(n log n) (most gap sequences)	O(n log^2 n) (best known worst case gap sequence)

공간 복잡도

전체 O(n), 보조 O(1)

 

특징

삽입정렬은 거의 정렬된 경우 빠르다

삽입 정렬은 삽입될 위치가 멀 경우 이동을 많이 해야하며 한 번에 한 요소의 위치만 결정됨

이러한 삽입 정렬의 장점을 살리고 단점을 보완한것이 셸 정렬이다

 

로직

gap만큼씩 떨어진 요소들을 추출해서 부분 배열을 만든다

gap의 초기값은 전체길이의 반이며 순회 할때마다 반으로 줄인다

(gap은 홀수인편이 속도가 빠르다)

만든 부분 배열을 삽입정렬을 한다

반복

 

예를 들어

[4, 3, 2, 1, 5, 6, 7]의 경우 처음 gap은 3

부분 배열

[4, 1, 7], [3, 5], [2, 6]을 각각 삽입정렬을 해서

[1, 3, 2, 4, 5, 6, 7]을 만든다

그 후의 gap은 1이므로 전체를 삽입정렬해서 정렬한다

 

코드

function shellSort(arr) {
  for (let gap = parseInt(arr.length / 2); gap > 0; gap = parseInt(gap / 2)) {
    // 홀수로 만들기 (홀수가 더 빠름)
    if (gap % 2 === 0) gap++;
    for (let i = 0; i < gap; i++) {
    // 부분 배열에 대한 삽입 정렬
      insertionSort(arr, i, arr.length - 1, gap);
    }
  }
  return arr;
}
function insertionSort(arr, first, last, gap) {
  let j = 0;
  let key = 0;
  for (let i = first + gap; i <= last; i = i + gap) {
    key = arr[i];
    for (j = i - gap; j >= first && arr[j] > key; j = j - gap) {
      arr[j + gap] = arr[j];
    }
    arr[j + gap] = key;
  }
}

let arr = [
  65, 73, 67, 98, 75, 80, 87, 30, 61, 45, 4, 36, 52, 5, 23, 68, 71, 70, 61, 21, 29, 73, 36, 90, 13,
  97, 14, 71, 1, 51, 49, 3, 15, 64, 51, 87, 80, 8, 73, 84, 21, 93, 46, 87, 49, 41, 77, 40, 73, 96,
];
console.log(shellSort(arr));

// 결과
[
   1,  3,  4,  5,  8, 13, 14, 15, 21, 21, 23,
  29, 30, 36, 36, 40, 41, 45, 46, 49, 49, 51,
  51, 52, 61, 61, 64, 65, 67, 68, 70, 71, 71,
  73, 73, 73, 73, 75, 77, 80, 80, 84, 87, 87,
  87, 90, 93, 96, 97, 98
]
comparisons : 201
swaps : 125

 

참고

[알고리즘] 셸 정렬(shell sort)이란 - Heee's Development Blog