SHELL SORT

Shell Sort

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, swappingelements. 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; }