Update CocktailShellSort.java

[fungamer2-2]

Cocktail Shell Sort now decreases the gap the gap by a factor of 2 instead of sqrt(2) Also, it no longer does a regular insertion sort on the last iteration.

[Gaming32]

In the future, you might want to use the Ciura gap sequence, instead of generated numbers.

[chromi]

In general, Shellsort has a number of interesting sequences which all behave differently. The best ones tend to approximate a geometric series with ratio in roughly [2…4], while having at least consecutive elements mutually coprime. Here are a few that satisfy that criterion:

Sedgewick 1982: (1, 8, 23, 77, 281, …) f(k) = (1 << (2*k)) + (3 << (k-1)) + 1, for k >= 1 f(0) = 1

Sedgewick 1986: (1, 5, 19, 41, 109, …) f(even k) = 9 * ((1 << k) - (1 << (k/2)) + 1 f(odd k) = (8 << k) - (6 << ((k+1)/2)) + 1

Fibonacci squared: (1, 4, 9, 25, 64, …) f(k) = g(k+1)^2 g(0) = 1; g(k < 0) = 0 g(k) = g(k-1) + g(k-2)

Fibonacci cubed: (1, 8, 27, 125, 512, …) f(k) = g(k+1)^3 g(0) = 1; g(k < 0) = 0 g(k) = g(k-1) + g(k-2)

Generalised coprime generator: f(0) = 1 f(1) = a (eg. 4, 5, 6, 7) f(k) ~= f(k-1) * b (eg. sqrt(5), e, pi, phi^2, phi^3) gcd(f(k), f(m)) = 1 : ∀ (m < k) ∈ ℕ

The generalised coprime generator can also be used to extend well-known finite series such as Ciura's, and seems to work particularly well in that role. The Sedgewick and Fibonacci sequences are easier to write generating code for, and can be implemented in constant space.

[Gaming32]

Another sequences: gap = gap/2|1, gap=1; while (gap<size) gap=gap*3+1; while (gap>1) gap/=3;

Curious how this might look... 🤔 Might have to do a video on that!

[Gaming32]

Another sequences: gap = gap/2|1, gap=1; while (gap<size) gap=gap*3+1; while (gap>1) gap/=3;

Curious how this might look... Might have to do a video on that!

No, because you are banned.

I’m saying I might do a video on it. You don’t have to, and you also don’t have to watch it if you don’t want to.

[Gaming32]

Too bad you can’t convert PRs to discussions

[Gaming32]

This is spam and will not be tolerated

[Gaming32]

You can have the self-promotion in, but remove the putdowns of the repo you’re commenting on.

[Gaming32]

You can have the self-promotion in, but remove the putdowns of the repo you’re commenting on.

You literally have been found to be unethical. No more Array Visualizer 4.0.

I will not debate this right now. I have something more important I’m doing rn.

[Gaming32]

In general, Shellsort has a number of interesting sequences which all behave differently. The best ones tend to approximate a geometric series with ratio in roughly [2…4], while having at least consecutive elements mutually coprime. Here are a few that satisfy that criterion:

Sedgewick 1982: (1, 8, 23, 77, 281, …) f(k) = (1 << (2*k)) + (3 << (k-1)) + 1, for k >= 1 f(0) = 1

Sedgewick 1986: (1, 5, 19, 41, 109, …) f(even k) = 9 * ((1 << k) - (1 << (k/2)) + 1 f(odd k) = (8 << k) - (6 << ((k+1)/2)) + 1

Fibonacci squared: (1, 4, 9, 25, 64, …) f(k) = g(k+1)^2 g(0) = 1; g(k < 0) = 0 g(k) = g(k-1) + g(k-2)

Fibonacci cubed: (1, 8, 27, 125, 512, …) f(k) = g(k+1)^3 g(0) = 1; g(k < 0) = 0 g(k) = g(k-1) + g(k-2)

Generalised coprime generator: f(0) = 1 f(1) = a (eg. 4, 5, 6, 7) f(k) ~= f(k-1) * b (eg. sqrt(5), e, pi, phi^2, phi^3) gcd(f(k), f(m)) = 1 : ∀ (m < k) ∈ ℕ

The generalised coprime generator can also be used to extend well-known finite series such as Ciura's, and seems to work particularly well in that role. The Sedgewick and Fibonacci sequences are easier to write generating code for, and can be implemented in constant space.

Woah! These are so cool! (also there’s a repo I saw once that had Ciura gaps or something similar like that coprime generator well into the millions)