Shell sort 에서의 간격?
shell sort에서 MarcinCiura의 연구에 의하면
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; }
