/*
 **************************************************************************
 * Program name : 048_Quick_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 Quick sort                         *
 *                (c) Try again ?                                         *
 **************************************************************************
*/
#include <iostream.h>
#include <stdlib.h>
#include <iomanip.h>

void Quicksort(int [], int, 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\tQuick 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";
     Quicksort(Number,0,Arraysize-1);
     for (Index=1; Index<=Arraysize; Index++)
       {
        cout << Number[Index-1];
        if (Index<Arraysize) cout << ", ";
       }

     // part 5 : try another set of numbers ?
     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 Quicksort(int Number[], int First, int Last)                    // Note (1)
{
 int Right, Left, Mid, Temp;

 Mid = Number[(First + Last) / 2];   // Find the value in the middle of the list
 Right = First;                      // Holds the position of the right most and
 Left  = Last;                       // left most element.
 do {
      while (Number[Right] < Mid) Right = Right + 1;
      while (Number[Left] > Mid) Left = Left - 1;
      if (Right <= Left)
        {
         Temp= Number[Right];
         Number[Right]= Number[Left];
         Number[Left]= Temp;
         Right = Right + 1;
         Left = Left - 1;
        }
     } while (Right <= Left);
  if (First < Left)
    Quicksort(Number, First, Left);
  if (Right < Last)
    Quicksort(Number, Right, Last);
}

/* Notes
   (1) The technique I use is "Quick Sort".
       THE QUICK SORT BEGINS BY ESTIMATING THE MIDRANGE VALUE IN THE ARRAY.
       ONCE THIS IS DETERMINED IT BREAKS THE ARRAY INTO PORTIONS, TO THE
       LEFT OF THE MIDRANGE AND TO THE RIGHT. EVERYTHING LESS THAN THE
       MIDRANGE GOES TO THE LEFT AND HIGHER TO THE RIGHT. IT BREAKS THESE
       TWO PORTIONS DOWN FURTHER REPEATING THIS PROCSS OVER UNTIL THE ARRAY
       HAS BEEN SORTED.

       Example :

       Pass             |     Elements in the array      |      Actions     |
       -----------------|--------------------------------|------------------|
       Before sorting   |       25, 12, 34, 64, 20       | Mid = 34         |
                        |            /          \        | swap 34 and 20   |
       1st pass         |     25, 12, 20      64, 34     | Mid = 12 and 64  |
                        |          |             |       | swap 12 and 25,  |
                        |          |             |       |      64 and 34   |
       2nd pass         |     12, 25, 20      34, 64     | Mid = 25         |
                        |     /     \                    | swap 20 and 25   |
       3rd pass         |   12     20, 25                |                  |
       -----------------|--------------------------------|------------------|
*/