shellSort.java

/**
* 셸 정렬에 의해 나누어진 부분 배열을 정렬할 삽입 정렬 알고리즘 
* @param array 배열
* @param startIndex 시작 인덱스
* @param gap 증분 
*/
void customInsertionSort(int[] arr, int startIndex, int gap) {
  for(int i = startIndex + gap; i < arr.length; i+=gap) { 
    // 삽입정렬과 다르게 i가 startIndex + gap에서 시작하고 증분이 1이 아니고, gap이 된다.
    int ai = arr[i];
    int j;
    for (j = i; j > startIndex && arr[j-1] > ai; j--) // j > 0 대신 j > startIndex 사용
      arr[j] = arr[j - 1];
    while (j > gap && arr[j-gap] > ai) { // arr[j-1] 대신에 arr[j-gap] 을 사용 
      arr[j] = arr[j-gap]; // arr[j-1] 대신에 arr[j-gap] 을 사용
      j -= gap;
    }
    arr[j] = ai;
  }
}

// 쉘 정렬
void shellSort(int[] arr){
  for(int gap = arr.length/2; gap > 0; gap /= 2) { // main loop, gap 을 2씩 나눔.. 4, 2, 1
    for (int startIndex = 0; startIndex < gap; startIndex++) 
      customInsertionSort(arr, startIndex, gap);
  }
}