/*
 **************************************************************************
 * Program name : 055_Shell_sort(Version_A) (Version 1.00)                *
 * Author       : Duck Wong                                               *
 * Language     : C / C++                                                 *
 * Compiler     : Boodshed Dec-C++ compiler Ver 3.95                      *
 * Computer     : PII350                                                  *
 * O/S          : Windows 98                                              *
 **************************************************************************
 * Version 1.00 : 2000/06/30 - first version                              *
 **************************************************************************
 * Description  : (a) Input a list of numbers                             *
 *                (b) Sort the list by Shell sort                         *
 *                (c) Try again ?                                         *
 **************************************************************************
*/
#include <iostream.h>
#include <stdlib.h>
#include <iomanip.h>

void Shellsort(int [], const int );

int main()
{
 // part 1 : declaration
 const int Arraysize=15;             // Maximum no. of element 15
 int   Number[Arraysize];            // Define the array Number
 int   Index;                        // loop counter
 char  Again;                        // Try again ?

 do {
     // part 2 : Input 15 real numbers
     cout << "\n\t\tShell_sort (Version 1.00)\n";
     cout << "\nPlease input 15 integer numbers (1 - 99), then this program"
          << "\nwill printed the list in both unsorted and sorted orders.\n\n";
     for (Index=1; Index<=Arraysize; Index++)
       do
         {
          cout << "The #" << Index << " number is : ";
          cin  >> Number[Index-1];
         } while ((Number[Index-1]<1) || (Number[Index-1]>99));

     // part 3 : List in unsorted order and call the function to sort the list
     cout << "\n\n    Sorting : ";
     for (Index=0; Index<Arraysize; Index++)
       cout << setw(4) << Number[Index];
     Shellsort(Number,Arraysize);

     // part 5 : try another number ?
     cout << "\n\n\t\aTry another set of numbers (Y/N) : ";
     cin  >> Again;
     cout << "\n";
    }while (Again=='Y' || Again=='y');
 cout << "\n" << endl;

 system("PAUSE");
 return 0;
}


void Shellsort(int Number[], const int Arraysize)                    // Note (1)
{
 int Index, Index_1, Index_2;         // Loop counters.
 unsigned int Gap;                    // Holds the value of gap
 int Temp;                            // Holds valus while swaping
 int Pass = 1;

 for (Gap = (Arraysize / 2); Gap > 0; Gap = Gap==2 ? 1 : Gap/2.2)    // Note (2)
   {
    for (Index_1 = Gap; Index_1 < Arraysize; Index_1++)
      {
       Temp = Number[Index_1];
       for (Index_2 = Index_1; Index_2 >= Gap && Temp < Number[Index_2-Gap];
            Index_2-=Gap)
         Number[Index_2] = Number[Index_2 - Gap];
       Number[Index_2] = Temp;
      }
    cout << "\n    Pass #" << Pass++ << " : ";
    for (Index=0; Index<Arraysize; Index++)
      cout << setw(4) << Number[Index];
    }
}

/* Notes
   (1) The technique I use is "Shell sort".
       Shell's idea was to avoid the large amount of data movement by first
       comparing elements that were far apart, then elements that were less
       far apart, until gradually shrinking toward the basic insertion sort.

       Example :

       Pass             |   Numbers
       -----------------|-----------------------
       Before sorting   |   25, 12, 34, 64, 20
       1st pass         |   20  12  25  64  34
       2nd pass         |   12  20  25  34  64
       -----------------|-----------------------

   (2) (a) Use either statement

           for (Gap = (Arraysize / 2); Gap > 0; Gap = Gap==2 ? 1 : Gap/2.2)
             or
           for (Gap = (Arraysize / 2); Gap > 0; Gap /= 2)

       (b) The gap between elements to be compared. After each pass of gap
           insertion sort is executed, the elements separated by a distance
           of Gap in the array are sorted. When Gap is 1, the loop is
           identical to insertion sort.
*/