CODEWITHSUNDEEP
calgorithmsortingshellsort
jimo
jimo

Reputation: 602

Implementing shellsort algorithm in C

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;
            }
        }
    }
 }

In this shellsort() function, we've j-=gap. Assuming n = 10, the gap is always 5 and j increments from 0,1,2,3,4....

It means the first 5 times this inner for loop runs, it will return a negative value to j (e.g. 0-5=-5), and thus since j will not be greater than or equal to 0, it will only run once.

It works because that is exactly what we want. We don't want to swap more than once, because if we did, we would only be swapping the same two values over again, thus causing unnecessary redundancy.

So, I was thinking why can't we just omit j-=gap from the loop as it doesn't seem to affect the functioning at all. Is there any special reason why j-=gap is included?

Am I missing something here?

Upvotes: 4

Views: 596

Answers (1)

templatetypedef
templatetypedef

Reputation: 373012

It might help to take a look at insertion sort as a reference to see where this comes from. In insertion sort, we scan from left to right, swapping each element backwards until it's greater than the element that comes before it (or it gets back to the start of the array). The pseudocode for that algorithm is shown here:

for (int i = 1; i < n; i++) {
   for (int j = i - 1; j > 0 && A[j + 1] > A[j]; j--) {
      swap(A[j], A[j - 1]);
   }
}

The outer loop ranges over all elements of the array, saying "put each one in place." The inner loop says "keep swapping the current element with the one that comes before it as long as there is an element that comes before it and that element is greater than it." Here, the use of +1, ++, -1, and -- are because we're constantly looking at the element that comes immediately before the current element.

In shellsort, we run multiple passes of this algorithm over the array, except that we don't use a step size of one. Instead, we use a step size of some amount called the gap amount. Shellsort therefore looks something like this:

for (each gap size) {
   for (int i = gap; i < n; i += gap) {
      for (int j = i - gap; j > 0 && A[j + gap] > A[j]; j -= gap) {
         swap(A[j], A[j - 1]);
      }
   }
}

The idea is that each element should be continuously compared against the element that's gap elements before it. If it's less than that number, we want to swap it with the preceding element, but then need to repeatedly compare it with the new element that precedes it.

As an example, suppose we are shellsorting this array of length 6:

6 5 4 3 2 1

After the first pass of shellsort (gap = 3), the array looks like this:

3 2 1 6 5 4

Now, imagine that we do the second pass of shellsort with gap = 1. The inner loop currently says "repeatedly swap every element backwards toward the front until it comes to rest." If you remove the j -= gap step from that loop, then every element is just compared against the one directly before it. That would result in the following. In each of these snapshots, the carats refer to where the swaps are looking:

3 2 1 6 5 4   ->   2 3 1 6 5 4
^ ^

2 3 1 6 5 4   ->   2 1 3 6 5 4
  ^ ^

2 1 3 6 5 4
    ^ ^

2 1 3 6 5 4   ->   2 1 3 5 6 4
      ^ ^

2 1 3 5 6 4   ->   2 1 3 5 4 6
        ^ ^

Notice that the resulting array is not sorted. However, if we put back the j -= gap code into the mix, then the following will happen instead:

3 2 1 6 5 4   ->   2 3 1 6 5 4
^ ^

2 3 1 6 5 4   ->   2 1 3 6 5 4   ->   1 2 3 6 5 4
  ^ ^              ^ ^

1 2 3 6 5 4
    ^ ^

1 2 3 6 5 4   ->   1 2 3 5 6 4
      ^ ^

1 2 3 5 6 4   ->   1 2 3 5 4 6   ->   1 2 3 4 5 6
        ^ ^              ^ ^

As you can see, now everything gets sorted properly.

Upvotes: 3

Related Questions