Loading…
Loading…
A gap-based generalization of insertion sort: sort elements far apart first, shrinking the gap until it becomes a final pass of ordinary insertion sort.
Gap = 8.
1void shellSort(int[] arr) {2 int n = arr.length;3 for (int gap = n/2; gap > 0; gap /= 2) // shrink the gap4 for (int i = gap; i < n; i++) { // gapped insertion5 int key = arr[i], j = i; // element to place6 while (j >= gap && arr[j-gap] > key) { // shift gapped elements7 arr[j] = arr[j-gap]; j -= gap;8 }9 arr[j] = key; // drop key in place10 }11}