/*
 **************************************************************************
 * Program name : 056_Shell_sort(Version_B) (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
 char Goahead;                             // Controlling changes in Gap
 char Sortagain;                           // Monitoring exchanges
 int Pass = 1;

 Sortagain = 'Y';
 Goahead = 'Y';
 Gap = Arraysize / 2;
 while (Gap>0)
   {
    Sortagain = 'Y';                       // Initial value of Sortagain is 'Y'
    while (Sortagain == 'Y')
      {
       Goahead = 'N';                      // Change to 'N' just before starting
                                           // a set of  cycles in the inner loop
       for (Index_1 = 0; Index_1 < (Arraysize - Gap); Index_1++)
         {
          if (Number[Index_1] > Number[Index_1+Gap])
            {
             Temp = Number[Index_1];
             Number[Index_1] = Number[Index_1+Gap];
             Number[Index_1+Gap] = Temp;
             Goahead = 'Y';                // Swapping has taken place
            }
         }
       if (Goahead != 'Y') Sortagain = 'N';
      }
   cout << "\n    Psss #"  << Pass++ << " : ";   // show the result of each pass
   for (Index=0; Index<Arraysize; Index++)
     cout << setw(4) << Number[Index];
   Gap = Gap / 2;
  }
}

/* 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 :

       --------|--------------------------------------------------------------
       Sorting |   31  26  25  14  47  10  30  25  36  96  65  94  57  55  72
       --------|--------------------------------------------------------------
       Psss #1 |   25  26  25  14  47  10  30  31  36  96  65  94  57  55  72
       Psss #2 |   14  26  10  25  31  25  30  47  36  57  55  72  96  65  94
       Psss #3 |   10  14  25  25  26  30  31  36  47  55  57  65  72  94  96
       --------|--------------------------------------------------------------
*/