// template functions: data type not specified before use. T is a type variable;
// when a template function is used, the type is specified.
/***************************************************************
quick sort
***************************************************************/

#include <iostream.h>
#include <stdio.h>
#include <fstream.h>
#include <assert.h>

template<class T>                      // Function prototype must be placed 
void quickSort(T a[], int l, int r);   // somewhere before the function is called.

									   // Function prototype can be omitted only when 
									   // the function is defined before it is called.
							           // Remove the prototype and run the program; 
                                       // what happens?

									   // template ==> type T is not specified before 
									   // the function (quickSort) is called. This is 
									   // flexible.

									   // a, l, r are formal parameters; 
									   // y, low, high below are actual parameters.
ofstream out("qsort.out");             // open a file called qsort.out; write result in the file

static int LOW, HIGH;                  // global variables, declared outside every function

void main(void)
{
   int y[16] = {15, 14, 13, 12, 11,   10, 9, 8, 7, 6, 5, 4, 3, 2, 1,    30};

   int low = 5, high = 14;    // low = 0, high = 15;

		LOW = low; HIGH = high;
        assert(out);
        out << "original list from index " << low << " to " << high << " is " << endl;
        for (int k=LOW; k<=HIGH; k++)  out << y[k] << ' ';    
		out << endl;
		out << "here is how quick sort works: " << endl;

   quickSort(y, low, high);
        out.close();                        // close the file

   for (int i = low; i <= high; i++)
	   cout << y[i] << ' ';
   cout << endl;
}


template<class T>                      // Swap is defined before it is explicitly called 
inline void Swap(T& a, T& b)
{// Swap a and b.
   T temp = a; a = b; b = temp;
}


template<class T>
void quickSort(T a[], int l, int r)
{ 
   for (int k=LOW; k<=HIGH; k++) out << a[k] << ' ';// write the process in file qsort.out
   out << endl;
											// a[0.....l ..... r .....]
											// Sort a[l:r], a[r+1] has large value.
   if (l >= r) return;                      // either sorted (if =) or error input (if >)
   int i = l,                               // left-to-right cursor; 
								     // ** passed value; necessary if passed by reference
       j = r + 1;                           // right-to-left cursor
   T pivot = a[i];                          // pivot = leftmost element

   // swap elements >= pivot on left side
   // with elements <= pivot on right side
   while (true) 
   {
      do 
	  {                                     // find >= element on left side of segment
         i = i + 1;
      }  while (a[i] < pivot);              // * loop breaks when 1st a[i] > pivot found

      do 
	  {                                     // find <= element on right side of segment
         j = j - 1;
      }  while (a[j] > pivot);              // ** loop breaks when 1st a[j] < pivot found

      if (i >= j) break;                    // swap pair not found; 
										    // so left elements < pivot < right elements

      Swap(a[i], a[j]);                     // Swap above 2 elements found in * and **
   }

   // place pivot(s)
   a[l] = a[j];
   a[j] = pivot;

   quickSort(a, l, j-1); // sort left segment
   quickSort(a, j+1, r); // sort right segment
}