[JS] 셸 정렬

1. 셸 정렬

 셸 정렬은 일정한 간격으로 떨어져 있는 자료들끼리 부분집합을 구성하고 각 부분집합에 있는 원소들에 대해서 삽입 정렬을 수행하는 작업을 반복하면서 전체 원소들을 정렬하는 방법이다. 전체 원소에 데헤 삽입 정렬을 수행하는 것보다 부분집합으로 나누어 정렬하면 전체 연산 횟수를 줄일 수 있다.

 

 

 셸 정렬에서 부분집합을 만드는 기준이 되는 간격을 매개변수 h에 저장한다. h에 대해 h가 1이 될 때까지 1/2씩 감소시키고, 각 단계마다 셸 정렬을 순환 호출한다. 처음에 h는 입력 배열의 길이에 1/2한 자연수를 초기화 값으로 받는다. 셸 정렬의 전체 연산 횟수는 간격 h에 의해 영향을 받기 때문에 알고리즘의 성능을 분석하기가 쉽지 않다. 일반적으로 셸 정렬의 시간 복잡도를 

$$ O(n^{1.25}) $$

 로 측정한다.

 

 

2. 동작 순서

 셸 정렬의 동작 순서를 간단한 예제를 이용하여 설명하도록 하겠다. 먼저 배열 [69, 10, 30, 2]을 입력받았다고 가정하자. 그리고 이 문제의 목적은 셸 정렬을 이용하여 입력배열을 오름차순으로 정렬하는 것이다.

 

 

 우리는 첫 간격을 초기화 할 때 입력 배열의 길이/2의 공식을 쓰기로 했다. 따라서 h의 첫 값은 4/2 = 2가 된다. h는 2이므로, 간격이 2인 원소들을 부분집합으로 묶으면 밑의 그림과 같이 두 개의 부분집합이 만들어진다.

 

 

각 부분집합에 대하여 삽입 정렬을 수행한다.

 

 

 h를 2로 나눈다. h는 1이 된다. 따라서 간격이 1인 원소들을 묶으면 한 개의 부분집합이 만들어진다.

 

 

 한 개의 부분 집합을 삽입 정렬을 이용하여 오름차순으로 정렬한다.

 

 

3. 프로그램 코드

const arr = [69, 10, 30, 2, 16, 8, 31, 22];

console.log("정렬 전");
console.log(arr);

console.log("\n\n정렬 후");
console.log(shellSort(arr));

function shellSort(arr){
  const h = parseInt(arr.length/2);

  for(let i=h; i>0; i= parseInt(i/2)){
    for(let j=0; j<h; j++){
      arr = intervalShort(j, i, arr);
    }
  }
  return arr;
}

function intervalShort(start, h, arr){
  const end = arr.length - h + start;
  let idx = end;

  while(idx > start){
    if(arr[idx-h] > arr[idx]){
      let temp = arr[idx];
      arr[idx] = arr[idx-h];
      arr[idx-h] = temp;
    }
    idx -= h;
  }

  return arr;
}

 

 

4. 참고 자료 

자바로 배우는 쉬운 자료구조, 한빛 미디어