1. ## Shell Sort

Today I studied the following shell sort code:

Code:
```void shellsort(int v[], int n)
{
int gap, i, j, temp;

for (gap = n/2; gap > 0; gap /= 2)
for(i = gap; i < n; i++)
for (j=i-gap; j>= 0 &&
v[j]>v[j + gap]; j-=gap){
temp = v[j];
v[j] = v[j + gap];
v[j+gap] = temp;
}

}```
I follow it all except for one part. In the innermost loop, the final loop expression:

Code:
`j -= gap`
What is the point of this? Can you not just write this loop as:

Code:
`for (j=i-gap; j>= 0 && v[j]>v[j + gap];)`
and have the second loop control the amount of times elements are compared?

Cheers

BIOS

2. What loop do you mean with "second loop"? The one that increments "i"? How will that one influence what goes on inside the "j" loop?

3. Originally Posted by TheBigH
What loop do you mean with "second loop"? The one that increments "i"?
Yep. There are three loops in the code example. The second one contains the i increment.

Originally Posted by TheBigH
How will that one influence what goes on inside the "j" loop?
Well it controls how often the j loop executes i.e. it will always ensure the j loop executes at least (n - gap) times on each iteration of the outermost loop.

4. The point of a shell sort is to sort every gap-th element. You start with a wide gap, like N/2, then reduce that until the gap is 1. The changing of the gap size is your outer loop. The middle loop makes sure that you cover all the elements when your gap size is not 1. The inner loop steps through the data in increments of gap, sorting elements at 0*gap, 1*gap, 2*gap, etc. Not changing j would amount to only looking at, 0*gap and 1*gap. Sure, you could probably remove that and alter your i loop to "pick up the slack", but then you no longer have a shell sort. It would become something else.

Read Shell sort - Wikipedia, the free encyclopedia, and look closely at the following diagram that article: File:Shellsort.svg - Wikipedia, the free encyclopedia.

The different rows correspond to your outer loop, reducing gap until it's 1. In an individual row, the different colored numbers represent the iterations of the i loop. The numbers of one color (e.g. all red numbers) correspond to the numbers examined/swapped by the j loop. If you didn't do j -= gap, you would only examine one pair of numbers for each color, instead of the whole array.

5. What's ironic, is I wrote that Shell sort, from the description of it, on Wikipedia.

My previous Shell sort was fubar'd from tinkering with it so much.

6. Can I ask why you did a swap instead of a shift? The wiki code did a shift.

7. Well, I just posted my Shell sort example in BIOS's thread, so I thought this was my code, but it's NOT.

I HATE Shell sort's with a swap, instead of a shift! There's a lot of Shell sort's out there that have this swap code in it, and it is entirely wrong.

This is how it should be, imo:

Code:
```//Shell sort Brand new, not optimized
void shellSort(int a[], int hi) {
int i, j, gap, temp;

for(gap = hi/2; gap > 0; gap /= 2) { //original Shell divisor
for(i = gap; i < hi; i++) {
temp = a[i];
j = i;
while(j>= gap && a[j-gap] > temp) {
a[j] = a[j - gap];
j = j - gap;
}
a[j] = temp;
}
}
}```
This is still unoptimized, but that is also, original Shell code, as I understand it.

BIOS, why'd you change my Shell code, dammit?

Well, I just posted my Shell sort example in BIOS's thread, so I thought this was my code, but it's NOT.

I HATE Shell sort's with a swap, instead of a shift! There's a lot of Shell sort's out there that have this swap code in it, and it is entirely wrong.

This is how it should be, imo:

Code:
```//Shell sort Brand new, not optimized
void shellSort(int a[], int hi) {
int i, j, gap, temp;

for(gap = hi/2; gap > 0; gap /= 2) { //original Shell divisor
for(i = gap; i < hi; i++) {
temp = a[i];
j = i;
while(j>= gap && a[j-gap] > temp) {
a[j] = a[j - gap];
j = j - gap;
}
a[j] = temp;
}
}
}```
This is still unoptimized, but that is also, original Shell code, as I understand it.

BIOS, why'd you change my Shell code, dammit?
Sure, you can optimize that further by replacing Shell's original increment sequence with a non-suckful one. Another, minor, improvement you can make is to swap the order of the two things in the while statement, since a[j-gap]>temp is less likely to be true than j>=test for any given test.

9. Agreed on the shift rather than swap. I take it one step further and don't do either if the first comparison indicates it wont need to move at all.

Here's the one off my website. This is using one of the best, if not the best, known gap sequences:
Code:
```template <class T>
void ShellSort(T a[], int n) {
//Incerpj-Sedgewick 1985
const int incs[] = {
1, 3, 7, 21, 48, 112,
336, 861, 1968, 4592, 13776,
33936, 86961, 198768, 463792, 1391376,
3402672, 8382192, 21479367, 49095696, 114556624,
343669872, 52913488, 2085837936};
for (int l = sizeof(incs)/sizeof(incs[0]); l > 0;) {
const int m = incs[--l];
for (int i = m; i < n; ++i) {
int j = i - m;
if (a[i] < a[j]) { //check if the item needs inserting first (eliminates redundant copying)
const T tempItem = a[i];
do {
a[j+m] = a[j];
j-=m;
} while ((j >= 0) && (tempItem < a[j]));
a[j+m] = tempItem;
}
}
}
}```
Well it's C++, but I'm sure that doesn't really change anything here.
The extra 'if' makes it faster for when the type being sorted isn't as small or trivial as an int.

I find that it's much easier to understand if you compare it to an insertion sort implementation.
Here's mine which is obviously implemented in the same style:
Code:
```template <class T>
void InsertionSort(T a[], int n) {
for (int i = 1; i < n; ++i) {
//check if the item needs inserting first (eliminates redundant copying)
if (a[i] < a[i - 1]) {
int j = i - 1;
const T tempItem = a[i];
//move items along while looking for the correct place
do {
a[j + 1] = a[j];
--j;
} while ((j >= 0) && (tempItem < a[j]));
//copy item into position
a[j + 1] = tempItem;
}
}
}```
If you can understand the later then you should be able to understand the former.

BIOS, why'd you change my Shell code, dammit?
Haha. Blame Kernighan and Ritchie. It's their code! :P

@Anduril462 thanks for the explanation.

Re: use of swap. It's taken from the C programming language 2nd ed. Nothing intentional on my part. Can I ask what the difference is between a swap and a shift?

11. Shift vs. swap in Shell sort:

1) Historical accuracy. Shell sort *is* Insertion sort, with the extra gap feature. Insertion sort uses shifts, not swaps.

2) Shifts should be slightly faster, although I haven't actually tested that, since reason #1 was enough for me to prefer shifts.

An example of a shift:

Code:
```value: 8 at set[1], is being placed
in set: {5,8,2,4,1,3,7,9}

8 is pulled out to a variable
set is ready to be shifted: {5,_,2,4,1,3,7,9}
2->[1], 4->[2], 1->[3], 3->[4], 7->[5] (all shifted to the left 1 place)```
Since 8 is < 9, 8 is "dropped" into set[6], and 9 is not moved. One shift loop has ended.

No wonder Shell sort is so often seen with swaps instead of shifts! I'm sure I've used K&R's version of Shell sort before, since it's right next to me when I program -- ACK!

Thanks for an optimized version, iMalc, and the tips, TheBigH.