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

void Selectionsort(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\tSelection_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];
        if (Index<Arraysize) cout << ", ";
       }

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

     // 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 Selectionsort(int Number[], int Arraysize)                      // Note (1)
{
 int Index_1, Index_2;         // Loop counters.
 int Min;                      // Holds the min values in the unsorted list.
 int Minpos;                   // Holds the position that stores the smallest
                               // value in the unsorted list.

 for (Index_1=0; Index_1<=Arraysize-2; Index_1++)
   {
    Min = Number[Index_1];
    Minpos = Index_1;
    for (Index_2=Index_1+1; Index_2<=Arraysize-1; Index_2++)
      if (Number[Index_2]< Min)
        {
         Min = Number[Index_2];
         Minpos = Index_2;
        }
    Number[Minpos] = Number[Index_1];
    Number[Index_1] = Min;
   }
}

/* Notes
   (1) The technique I use is "Selection sort".
       THIS PROGRAM FIND THE SMALLEST ELEMENT AND EXCHANGE IT WITH THE FIRST
       IN YOUR LIST. THEN FIND THE SECOND SMALLEST AND EXCHANGE IT WITH THE
       ONE AT POSITION TWO. CONTINUE DOING THIS UNTIL THE WHOLE LIST IS SORTED.

       Example :

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