정렬 알고리즘 - 쉘 정렬

쉘 정렬(Shell Sort)

• 쉘 정렬은 일정 간격으로 떨어진 원소들끼리 부분집합을 구성하고 각 부분집합의 원소들에 대하여 삽입 정렬을 수행하는 작업을 반복하여 전체 원소들을 정렬하는 알고리즘이다.
• 전체 비교 정렬이며, 삽입 정렬을 개선한 정렬방법이다.
• 멀리 떨어진 원소들 끼리 정렬 한 다음 비교할 원소 사이 간격을 점진적으로 줄여 나간다.

시간복잡도

• 최선의 경우 : O(n)
• 최악의 경우 : O(n^2)
  
  

장점

• 멀리 떨어져 있는 원소를 교환하기 때문에 입력 자료에 민감하지 않다.
  
  

단점

• 원소사이의 간격을 잘못 설정하면 성능이 O(n^2)으로 악화된다.
  
  

구현

'use strict';

function ShellSort(arr) {
  let gap = parseInt(arr.length / 2);

  while (gap > 0) {
    for (let i = 0; i < arr.length - gap; i++) {
      let curIdx = i;
      let shiftIdx = i + gap;

      while (curIdx >= 0) {
        if (arr[curIdx] >= arr[shiftIdx]) {
          [arr[curIdx], arr[shiftIdx]] = [arr[shiftIdx], arr[curIdx]];
        }

        shiftIdx = curIdx;
        curIdx -= gap;
      }
    }

    gap = parseInt(gap / 2);
  }

  return arr;
}

console.log(ShellSort([1, 3, 5, 6, 2, 0, 8, 9, 7, 4]));