/*
 **************************************************************************
 * Program name : 041_Insertion_sort (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/15 - first version                              *
 **************************************************************************
 * Description  : (a) Input a list of numbers                             *
 *                (b) Sort the list by Insertion Sort                     *
 *                (c) Try again ?                                         *
 **************************************************************************
*/
#include <iostream.h>
#include <stdlib.h>
#include <iomanip.h>

void Insertionsort(int [], const int);

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

 do {
     // part 2 : Input 15 real numbers
     cout << "\n\t\tInsertion 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
     cout << "\n\nThe unsorted list is : \n";
     for (Index=1; Index<=Arraysize; Index++)
       cout << Number[Index-1] << ", ";

     // part 4 : List in sorted order
     cout << "\n\nThe sorted list is : \n";
     Insertionsort(Number, Arraysize);
     for (Index=1; Index<=Arraysize; Index++)
       cout << Number[Index-1] << ", ";

     // 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 Insertionsort(int Number[], int Arraysize)                      // Note (1)
{
 int Index, Tempkey, Tempint;
 char Found;

  for (Index= 1; Index<=Arraysize-1; Index++)
    if (Number[Index]<Number[Index-1])
      {
       Tempint = Number[Index];
       Tempkey = Index;
       do
         {
          Tempkey = Tempkey-1;
          Number[Tempkey+1] = Number[Tempkey];
          if (Tempkey==0)
            Found = 'Y';
          else
            {
             if (Number[Tempkey-1]<=Tempint)
               Found = 'Y';
             else
              Found = 'N';
            }
         } while (Found != 'Y');
       Number[Tempkey] = Tempint;
      }
}


/* Notes
   (1) The technique I use is "Insertion sort". Every pass, the first number
       in the unsorted list will be place at the right position in the sorted
       list.

       Example :

       Pass              |   Sorted elements     | Unsorted Numbers
       ------------------|-----------------------|------------------------
       Before sorting    |                       | 25, 12, 34, 31, 20
       Ignore 1st number |   25                  |     12, 34, 31, 20
       1st pass          |   12, 25              |         34, 31, 20
       2nd pass          |   12, 25, 34          |             31, 20
       3rd pass          |   12, 25, 31, 34      |                 20
       4th pass          |   12, 20, 25, 31, 34  |
       End of sorting    |                       |
       ------------------|-----------------------|------------------------
       No. of pass is equal to no. of item less one.
*/