Shell sort 에서의 간격?

MarcinCiura의 연구에 의하면,

shell sort에서 1,4, 10, 23, 57, 132, 301, 701, 1750 … 과 같은 간격을 사용하는게 연산 시간을 많이 줄인다고 한다..

그러면 이것이 다른 분할 규칙에서도 유용할 것인가?

그리고.. 당췌 위 기준은 무엇을 기준으로 완성된 기준일까??

하여 아래와 같은 것을 찾았다.

---

Optimal gap

The fundamental problem of Shell sort is to determine the optimal gap between compared elements. In the original algorithm Donald Shellproposed an initial gap of size ( is the size of the array), divided by in each step. Thich approach has one big disadvantage – elements at odd and even places are mutually compared only in the last step.

Other implementations used gap size (Hibbard) with the worst case complexity , or (Sedgewick) with complexity . The best performance is offered by a sequence by Marcin Ciura - 1, 4, 10, 23, 57, 132, 301, 701, 1750 every next gap size is generated by multiplying the previous size by .

출처: http://en.algoritmy.net/article/41653/Shell-sort

/**
* Shell sort - sort with diminishing increment (descending)
* @param array to be sorted
* @param size array size
* @return sorted array
*/
int * shellSort(int * array, int size) {
   int gap = size / 2;
   while (gap > 0) {
       for (int i = 0; i < size - gap; i++) { //modified insertion sort
           int j = i + gap;
           int tmp = array[j];
           while (j >= gap && tmp > array[j - gap]) {
               array[j] = array[j - gap];
               j -= gap;
           }
           array[j] = tmp;
       }
       if (gap == 2) { //change the gap size
           gap = 1;
       } else {
           gap /= 2.2;
       }
   }
   return array;
}