[Algorithm] 셸 정렬(Shell Sort)

1. 셸 정렬(Shell Sort)이란?

이미지 출처: https://runestone.academy/ns/books/published/pythonds/_images/shellsortB.png

• 도날드 셸(D.L.Shell)이 고안한 알고리즘으로, 삽입 정렬(Insert Sort)의 장점을 살리고 단점을 보완하여 좀더 빠르게 정렬한다.
• 일정한 간격으로 서로 떨어져있는 두 요소를 그룹으로 묶어 대략 정렬을 수행하고 간격을 좁혀 그룹의 수를 줄이면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법이다. 즉 그룹 별로 미리 몇차례 정렬을 하고 삽입 정렬을 실시하여 삽입 정렬의 장점을 이용한다.
• 셸 정렬 과정에서 수행하는 각각의 정렬을 h-정렬이라고 한다.
• 멀리 떨어져있는 요소를 교환하므로 안정적이지 않다.
• 시간 복잡도는  O(n1.25)로 O(n^2)보다 빠르다.

1.1 동작 방법

배열이 { 8, 1, 4, 2, 7, 6, 3, 5 }라고 가정하고 셸 정렬을 수행하면 아래와 같이 동작한다.

1. 4칸 떨어져있는 요소를 모아 배열을 4개의 그룹({8,7}, {1,6}, {4,3}, {2,5})로 나누고 각 그룹별로 정렬한다.(4-정렬 수행) --> {7,8}, {1,6}, {3,4}, {2,5}
2. 4-정렬을 마친 상태에서 2칸 떨어진 요소를 모아 두 그룹({7,3,8,4}, {1,2,6,5})으로 나누어 2-정렬을 한다.(2-정렬 수행) --> {3,4,7,8}, {1,2,5,6}
3. 마지막으로 1-정렬을 적용하여 정렬한다. 

1.2 증분값(h값) 선택

• h값이 서로 배수가 되지 않도록 만들어야한다. 이렇게 하면 요소가 충분히 섞여 효율적으로 정렬할 수 있다.
• 1부터 시작하여 3배 더한 값에 1을 더하는 수열을 사용한다.

1.3 구현하기

public void shellSort(int[] arr, int n) {
  for(int h = n / 2; h > 0; h /= 2) {
    for(int i = h; i < n; i++) {
      int j;
      int temp = arr[i];
      for(j = i - h; j >= 0 && arr[j] > temp; j -= h) {
        arr[j + h] = arr[j];
      }
      arr[j + h] = temp;
    }
  }
}