I've been trying to teach myself various sort methods just for the sake of being able to use them in the future and right now I've been teaching myself about shell sorts. I understand the way shell sorts themselves work (they're in essence insertions sorts except it only occurs between gaps that progressively decreases in size, allowing items to be moved across "larger distances"). One thing that I've heard about this algorithm is that you do have freedom over how you choose your gap sequence, since apparently if you choose a bad one it can make the sequence less efficient than even normal insertion sort. This is how I got to introduced to Ciura's gap sequence (1, 4, 10, 23, 57, 132, 301, 701 etc if I'm not mistaken) and Sedgewick's gap sequence formula which I think is 4*9^i-9*2^i+1.
The part where my confusion begins is trying to use these in context to a shell sorting method. Just as an example I've been looking at a simple function for a shell sort written in Java by GeeksForGeeks.
public static void shellSort(int[] arr) {
int n = arr.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
I've spent about an hour or so trying to think about how this method could be refactored to use either Sedgewick's formula or Ciura's, but I've been stumped on this. For context I should say that the way I've been teaching myself these sort algorithms is by learning what the algorithm is both conceptually and from a basic code logic sense and then writing simple (but still fitting/functional) versions of them in Java so that I have a reference for applying them in other languages (since Java was the first language I learned). For example one problem that I've been thinking over is how 'large' the sequence should be. Should the first/highest gap value be equivalent to the array/structure's size or something else? Should the gap values then be stored in their own array to be referenced against the parameter, or should the for loop be able to handle that for me if I write it correctly?
I really wish I could crunch this question down into a TLDR, but I can't think of a good one as I've opted to lay out as much context to this as I could think of. Hopefully you can forgive me for that.
One idea could be to provide a stream of increasing gaps as second argument to the shellSort function. Then the caller can choose which gap sequence to provide. The sort function will then consume as many gaps as are needed for the given array, reverse that list of gaps, and then do the loop as you had it.
// Shell sort now takes a gap sequence as second argument
public static void shellSort(int[] arr, Stream<Integer> gapSequence) {
int n = arr.length;
// Collect gaps <= n
List<Integer> gaps = gapSequence
.takeWhile(g -> g < n)
.collect(Collectors.toList());
// Iterate gaps in reverse order
Collections.reverse(gaps);
for (int gap : gaps) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
// Example gap sequence: this is Sedgewick, 1986, sequence https://oeis.org/A033622
public static Stream<Integer> sedgewickSequence() {
return Stream.iterate(0, i -> i + 1)
.map(i -> 1 +
((9 - i % 2) << i) - (((3 - i % 2) * 3) << ((i + 1) / 2))
);
}
public static void main(String[] args) {
int[] arr = {23, 12, 1, 8, 34, 54, 2, 3, 18, 22, 6, 36, 7, 0, 27, 30, 11, 19, 14, 9};
shellSort(arr, sedgewickSequence());
System.out.println(Arrays.toString(arr));
}
For Ciura's gap sequence there is no known formula as it was experimentally derived. But you could still create an infinite stream that starts with the known Ciura values, and then continues with some chosen formula when larger gaps are needed:
public static Stream<Integer> ciuraSequence() {
return Stream.concat(Stream.of(1, 4, 10, 23, 57, 132, 301, 701, 1750), // Ciura -- empirical
Stream.iterate(1750, g -> (int)(g * 2.25))); // ...continuation after known gaps
}
Here is the same with generators in other languages:
// Helper function
function* takeWhile(iter, predicate) {
for (const value of iter) {
if (!predicate(value)) break;
yield value;
}
}
// Shell sort now takes a gap sequence as second argument
function shellSort(arr, gapSequence) {
const n = arr.length;
// Collect gaps <= n
const gaps = [...takeWhile(gapSequence, g => g < n)];
// Iterate gaps in reverse order
gaps.reverse();
for (const gap of gaps) {
for (let i = gap; i < n; i++) {
const temp = arr[i];
let j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
// Example gap sequence: this is Sedgewick, 1986, sequence https://oeis.org/A033622
function* sedgewickSequence() {
for (let i = 0; true; i++) {
yield 1 + ((9 - i % 2) << i) - (((3 - i % 2) * 3) << ((i + 1) / 2));
}
}
// main
const arr = [23, 12, 1, 8, 34, 54, 2, 3, 18, 22, 6, 36, 7, 0, 27, 30, 11, 19, 14, 9];
shellSort(arr, sedgewickSequence());
console.log(...arr);from itertools import takewhile, count
# Shell sort now takes a gap sequence as second argument
def shell_sort(lst, gap_sequence):
n = len(lst)
# Collect gaps <= n
gaps = list(takewhile(lambda g: g < n, gap_sequence))
# Iterate gaps in reverse order
gaps.reverse()
for gap in gaps:
for i in range(gap, n):
temp = lst[i]
for j in range(i, gap-1, -gap):
if lst[j - gap] <= temp:
break
lst[j], lst[j - gap] = lst[j - gap], temp
# Example gap sequence: this is Sedgewick, 1986, sequence https://oeis.org/A033622
def sedgewick_sequence():
for i in count(0):
yield 1 + ((9 - i % 2) << i) - (((3 - i % 2) * 3) << ((i + 1) // 2))
# main
lst = [23, 12, 1, 8, 34, 54, 2, 3, 18, 22, 6, 36, 7, 0, 27, 30, 11, 19, 14, 9]
shell_sort(lst, sedgewick_sequence())
print(*lst)