알고리즘 - 셀 정렬(shell sort) / 셀 정렬 구현

셀 정렬?

---

🔑 keyword : gap, 마지막엔 삽입 정렬

 

셀 정렬은 ‘Donald L. Shell’이라는 사람이 제안한 방법으로 삽입정렬을 보완한 알고리즘이다. 삽입 정렬은 크기가 크고 정렬되지 않은 배열을 처리하는데 느리다. 그러나 셀 정렬은 서로 멀리 떨어진 항목 간에도 교환이 일어날 수 있다. 그리고 삽입 정렬이 빠르게 처리할 수 있도록 부분적으로 정렬된 배열을 만든다.

 

📌 셀 정렬 동작 순서

1. 매 h번째 한목들 간에 삽입 정렬을 수행한다.
   • 부분적으로 정렬된 배열을 h-정렬 되었다고 한다.
   • 큰 h값에 대해 h-정렬을 해서 서로 멀리 떨어진 배열 항목들을 이동시킨다.
2. h값을 정해진 만큼 줄여나가서 1이 될 때까지 줄이면서 위의 과정을 반복한다.

 

📌 h-정렬

h-정렬된 배열은 서로 교차하며 존재하는 h개의 독립된 부분 정렬 시퀀스들이다.

 

📌 셀 정렬의 효율성

셀 정렬은 큰 배열에 대해서도 적절한 성능을 보여주며 추가적인 메모리를 사용하지 않는다.

	최선의 경우	평균의 경우	최악의 경우
셀 정렬	O(N)	O(N^3/2)	O(N^3/2)

 

Ex.

const exchange = (array, j, i) => { // gap의 위치와 현재 인덱스와 값 교환
  [array[j], array[i]] = [array[i], array[j]];
}

// array = [19, 8, 5, 12, 12, 19, 15, 18, 20, 5, 24, 1, 13, 16, 12, 5]
const shellSort = (array) => {
  let gap = Math.floor(array.length / 2); // 초기 gap 값 설정

  while(gap > 0){
    for(let i = gap; i < array.length; i++){
      for(let j = i; j >= 0; j = j - gap){ 

        if(array[j] < array[j - gap]){ // 배열의 순차적인 index와 gap 번째의 값과 비교
          exchange(array, j, j - gap);
        }else {
          break;
        }

      }
    }

    gap = Math.floor(gap / 2); // gap 값이 0이 될때까지 재설정
  }

	// array = [1, 5, 5, 5, 8, 12, 12, 12, 13, 15, 16, 18, 19, 19, 20, 24]
};

 

또는 Knuth's sequence 방식으로 비교적 큰 간격에서 시작해서 점차적으로 간격을 줄여나가는 방법으로 구현할 수 있다.

 

const exchange = (array, i, j) => {
  [array[i], array[j]] = [array[j], array[i]];
};

const shellSort = (array) => {
  const { length } = array;

  let gap = 1;
  while (gap < Math.floor(length / 3)) {
    gap = 3 * h + 1;
  }

  while (gap >= 1) {
    for (let i = gap; i < length; i++) {
      for (let j = i; j >= 0; j = j - h) {
        if (array[j] < array[j - gap]) {
          exchange(array, j, j - gap);
        } else {
          break;
        }
      }
    }

    gap = Math.floor(gap / 3);
  }
};