

The shell sort
is named after its inventor D. L. Shell. Instead of comparing
adjacent elements, like the bubble sort, the shell sort repeatedly
compares elements that are a certain distance away from each other (d
represents this distance).
The value of d starts out as half the input size and is halved after each pass through the
array. The elements are compared and swapped when needed. The equation
d = (N + 1) / 2 is used. Notice that only integer values are used for
d since integer division is occurring.

Let's look at our same list of values for descending order
with the shell sort. Remember, a "pass" is defined as one full
trip through the array comparing and if necessary, swapping
elements.
Array at beginning: 
84 
69 
76 
86 
94 
91 
d 
After Pass #1: 
86 
94 
91 
84 
69 
76 
3 
After Pass #2: 
91 
94 
86 
84 
69 
76 
2 
After Pass #3: 
94 
91 
86 
84 
76 
69 
1 
After Pass #4 (done): 
94 
91 
86 
84 
76 
69 
1 
First Pass: d =
(6 + 1) / 2 = 3. Compare 1st and 4th , 2nd and 5th, and 3rd and 6th items
since they are 3 positions away from each other))
Second Pass: value for d is halved
d = (3 + 1) / 2 = 2. Compare items two places away such as 1st and
3rd ……
Third Pass: value for d is
halved d = (2 + 1) / 2 = 1. Compare items one place away
such as 1st and 2nd …..
Last Pass: sort continues until d
= 1 and the pass occurs without any swaps.
This sorting process, with its comparison model, is an
efficient sorting algorithm.
//Shell Sort Function for Descending Order
void ShellSort( apvector <int> &num)
{
int i, temp, flag = 1, numLength = num.length( );
int d = numLength;
while( flag  (d > 1))
// boolean flag (true when not equal to 0)
{
flag = 0; // reset flag to 0 to check for future swaps
d = (d+1) / 2;
for (i = 0; i < (numLength  d);
i++)
{
if (num[i + d] > num[i])
{
temp = num[i + d];
// swap positions i+d and i
num[i + d] = num[i];
num[i] = temp;
flag = 1;
// tells swap has occurred
}
}
}
return;
}
