/*
set gap to size / 2
while gap > 0
{
  if the gap is 2, make it 1 - this will be the last pass 
       through the array.   
  /* consider each array as a set of "chains" of smaller arrays in
     which the elements of a chain are separated by the value of gap.
     We need to sort all the chains using insertion sort.
  */
  1. for each array element x[nextIndex] starting with the one at position 
     gap:
       2.  for each element in the sorted part starting with the last one
           (at position nextIndex - gap):
              3. if this element is larger than the one being inserted
                    shift it to the right.
       4.  Place the element being inserted at the position of the
           last element that was shifted.
  gap = gap / 2.2   // divide by 2.2 for better performance.
}  // end outer loop
*/




#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

void shellSort(int[], int);

int main()
{
   const int SIZE = 10000;
   int scores[SIZE];
   for (int i = 0; i < SIZE; i++)
     scores[i] = int(random() / 1000);
/*
   for (int i = 0; i < SIZE; i++)
      cout << scores[i] << ", ";
   cout << endl << endl << endl;
*/  
   shellSort(scores, SIZE);
   /*
   for (int i = 0; i < SIZE; i++)
      cout << scores[i] << ", ";
   cout << endl;
   */
   return 0;
}


void shellSort(int x[], int size) {
  int j, next;
 /*
 for each array element starting with the second one.
       2.  for each element in the sorted part starting with the last one
              3. if this element is larger than the one being inserted
                    shift it to the right.                                
 */
for (int gap = size / 2; gap >= 1; gap = gap / 2.2) 
{
 if (gap == 2) gap = 1;
 for (int nextIndex = gap; nextIndex < size; nextIndex++)
 {
    next = x[nextIndex];
    j = nextIndex - gap;
    while (j >= 0 && x[j] > next)
    {
       x[j+gap] = x[j];
       j -= gap;
    }

    x[j+gap] = next;
 }
}
}