Java를 사용하여 힐 정렬 알고리즘을 구현하는 간단한 예

소개
힐 정렬 (축소 증량법) 은 삽입 클래스 정렬에 속한다. 셸에 의하면 힐 정렬은 직접 삽입 정렬에 대해 간단하게 개선했다. 힐 정렬은 삽입 정렬에서 요소 간의 간격을 확대하고 이 간격이 있는 요소에 삽입 정렬을 해서 항목을 크게 이동시킨다. 이 데이터 항목이 한 번 정렬된 후에 힐 정렬 알고리즘은 데이터 항목의 간격을 줄이고 순서대로 정렬한다.이러한 정렬을 할 때의 데이터 항목 사이의 간격을 증량이라고 하는데, 습관적으로 알파벳 h로 이 증량을 표시한다.
자주 사용하는 h 시퀀스는 Knuth에서 제안합니다. 이 시퀀스는 1부터 시작하여 다음과 같은 공식을 통해 생성됩니다.

h = 3 * h +1

반대로 프로그램은 h시퀀스를 역계산해야 하기 때문에 사용해야 한다

h=(h-1)/3

코드 구현
구현 코드 1:

public static void shellSort(int[] arr){
  int temp;
  for (int delta = arr.length/2; delta>=1; delta/=2){               // 
    for (int i=delta; i<arr.length; i++){       
      for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){ // delta
        temp = arr[j-delta];
        arr[j-delta] = arr[j];
        arr[j] = temp;
      }
    }//loop i
  }//loop delta
}

구현 코드 2:

public static void shellSort2(int[] arr){
  int delta = 1;
  while (delta < arr.length/3){//generate delta
    delta=delta*3+1;  // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
  }    
  int temp;
  for (; delta>=1; delta/=3){
    for (int i=delta; i<arr.length; i++){       
      for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){
        temp = arr[j-delta];
        arr[j-delta] = arr[j];
        arr[j] = temp;
      }
    }//loop i
  }//loop delta
}

위의 프로그램은 직접 삽입법과 비교했을 때 직접 삽입 정렬과의 차이점을 발견할 수 있다. 직접 삽입 정렬의 h는 1로 대체된다.
셸 정렬이 불안정하고 공간 비용도 O(1)이며 시간 비용은 O(N3/2)~O(N7/6) 사이로 추정된다.