Thread: 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

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?

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?

Originally Posted by Adak

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.

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.

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.