/////////////////////
//                 //
// Dave S. Maynard //
// -- Daxxus       //
//                 //
/////////////////////
//                 //
//   March 2001    //
//                 //
/////////////////////

#include <iostream.h>
#include <stdlib.h>
#include <iomanip.h>
#include <time.h>
#include <string.h>
#include <math.h>
#include <list>

using namespace std;

//#define DEBUGIT

void mergeSort(int [], int, int, int []);
void Merge(int [], int, int, int, int []);

void insertionSort(int [], int);

void radix(int, int, int *, int *);
void radixSort(int *, int *, int);

void Heapify(int [], int, int);
void HeapSort(int [], int);
void BuildHeap(int [], int);

void insertionSort(list <float> &);
float* BucketSort(float [], int);

void Quicksort(int [], int, int);
void Swap(int [], int, int);
int Partition(int [], int, int);

void CountingSort(int [], int [], int, int);

void printResults(double, int);

#ifdef DEBUGIT
void printToScreen(int [], int, int);
void printToScreen(float [], int, int);
#endif

//////////
// Main //
//////////
void main()
{
int i = 0;
int startTime = 0;
int finishTime = 0;
double totalTime = 0.0;
int sampleSizeIndex;

int sampleSizes[] = {10, 50, 100, 500, 1000, 5000, 10000, 50000, 100000, 500000, 1000000};

cout << "Multi-Sort Program";

// Valid Input loop
while(1)
{
cout << endl << endl << "Sample Sizes:: ";
for(i = 0; i < 11; i++)
   cout << sampleSizes[i] << " ";
cout << endl << "Choices::       1  2   3   4    5    6     7     8      9     10      11" 
     << endl << endl << "Choose:: ";
cin >> sampleSizeIndex;
if((sampleSizeIndex < 1) || (sampleSizeIndex > 12))
   cout << "Your Choice must be between 1 and 12...";
else
   break;
}
cout << endl;

// Creation of the Random Data Array
int *rawData;
rawData = new int[sampleSizes[sampleSizeIndex - 1]];

// Seed
srand(time(NULL));

// Creation of the Random Data
for(i = 0; i < sampleSizes[sampleSizeIndex - 1]; i++)
   rawData[i] = rand();

cout << "Statistics::" << endl
     << "The Random Sample Size is " << sampleSizes[sampleSizeIndex - 1] << "." << endl << endl;

// MERGE SORT ///////////////////////////////////////////////
int *mergeData;
mergeData = new int[sampleSizes[sampleSizeIndex - 1]];

for(i = 0; i < sampleSizes[sampleSizeIndex - 1]; i++)
   mergeData[i] = rawData[i];

int *Temp;
Temp = new int[sampleSizes[sampleSizeIndex - 1]];

startTime = clock();
mergeSort(mergeData, 0, sampleSizes[sampleSizeIndex - 1] - 1, Temp);
finishTime = clock();

#ifdef DEBUGIT
printToScreen(mergeData, sampleSizes[sampleSizeIndex - 1], 100);
#endif

delete [] Temp;
delete [] mergeData;
 
totalTime = double(finishTime - startTime) / CLOCKS_PER_SEC;
printResults(totalTime, 0);
// END MERGE SORT ///////////////////////////////////////////

// INSERTION SORT ///////////////////////////////////////////
int *insertionData;
insertionData = new int[sampleSizes[sampleSizeIndex - 1]];

for(i = 0; i < sampleSizes[sampleSizeIndex - 1]; i++)
   insertionData[i] = rawData[i];

startTime = clock();
insertionSort(insertionData, sampleSizes[sampleSizeIndex - 1]);
finishTime = clock();

#ifdef DEBUGIT
printToScreen(insertionData, sampleSizes[sampleSizeIndex - 1], 100);
#endif

delete [] insertionData;

totalTime = double(finishTime - startTime) / CLOCKS_PER_SEC;
printResults(totalTime, 1);
// END INSERTION SORT ///////////////////////////////////////

// RADIX SORT ///////////////////////////////////////////////
int *radixData;
radixData = new int[sampleSizes[sampleSizeIndex - 1]];

for(i = 0; i < sampleSizes[sampleSizeIndex - 1]; i++)
   radixData[i] = rawData[i];

Temp = new int[sampleSizes[sampleSizeIndex - 1]];

startTime = clock();
radixSort(radixData, Temp, sampleSizes[sampleSizeIndex - 1]);
finishTime = clock();

#ifdef DEBUGIT
printToScreen(radixData, sampleSizes[sampleSizeIndex - 1], 100);
#endif

delete [] radixData;
delete [] Temp;

totalTime = double(finishTime - startTime) / CLOCKS_PER_SEC;
printResults(totalTime, 2);
// END RADIX SORT ///////////////////////////////////////

// HEAP SORT ///////////////////////////////////////////
int *heapData;
heapData = new int[sampleSizes[sampleSizeIndex - 1]];

for(i = 0; i < sampleSizes[sampleSizeIndex - 1]; i++)
   heapData[i] = rawData[i];

startTime = clock();
HeapSort(heapData, sampleSizes[sampleSizeIndex - 1]);
finishTime = clock();

#ifdef DEBUGIT
printToScreen(heapData, sampleSizes[sampleSizeIndex - 1], 100);
#endif

delete [] heapData;

totalTime = double(finishTime - startTime) / CLOCKS_PER_SEC;
printResults(totalTime, 3);
// END HEAP SORT ///////////////////////////////////////

// BUCKET SORT /////////////////////////////////////////
float *bucketData;
bucketData = new float[sampleSizes[sampleSizeIndex - 1]];

for(i = 0; i < sampleSizes[sampleSizeIndex - 1]; i++)
   bucketData[i] = (rand() % 1000) / 1000.0;

startTime = clock();
BucketSort(bucketData, sampleSizes[sampleSizeIndex - 1]);
finishTime = clock();

#ifdef DEBUGIT
printToScreen(bucketData, sampleSizes[sampleSizeIndex - 1], 100);
#endif

delete [] bucketData;

totalTime = double(finishTime - startTime) / CLOCKS_PER_SEC;
printResults(totalTime, 4);
// END BUCKET SORT ///////////////////////////////////////

// QUICK SORT ///////////////////////////////////////////
int *quickData;
quickData = new int[sampleSizes[sampleSizeIndex - 1]];

for(i = 0; i < sampleSizes[sampleSizeIndex - 1]; i++)
   quickData[i] = rawData[i];

startTime = clock();
Quicksort(quickData, 0, (sampleSizes[sampleSizeIndex - 1] - 1));
finishTime = clock();

#ifdef DEBUGIT
printToScreen(quickData, sampleSizes[sampleSizeIndex - 1], 100);
#endif

delete [] quickData;

totalTime = double(finishTime - startTime) / CLOCKS_PER_SEC;
printResults(totalTime, 5);
// END QUICK SORT ///////////////////////////////////////

// COUNTING SORT ///////////////////////////////////////////
int *countingData;
countingData = new int[sampleSizes[sampleSizeIndex - 1]];

Temp = new int[sampleSizes[sampleSizeIndex - 1]];

for(i = 0; i < sampleSizes[sampleSizeIndex - 1]; i++)
   Temp[i] = 0;

for(i = 0; i < sampleSizes[sampleSizeIndex - 1]; i++)
   countingData[i] = rawData[i];

startTime = clock();
CountingSort(countingData, Temp, 40000, sampleSizes[sampleSizeIndex - 1]);
finishTime = clock();

#ifdef DEBUGIT
printToScreen(Temp, sampleSizes[sampleSizeIndex - 1], 100);
#endif

delete [] countingData;
delete [] Temp;

totalTime = double(finishTime - startTime) / CLOCKS_PER_SEC;
printResults(totalTime, 6);
// END COUNTING SORT ///////////////////////////////////////

delete [] rawData;
cin.ignore();
cout << "Press [Enter] to Exit" << endl;
cin.get();
}

///////////////////////////
// recurseMerge Function //
///////////////////////////
void mergeSort(int array[], int i, int j, int Temp[])
{
int midpoint = 0;
   
// Array is empty
if(i == j)
   return;
   
// Midpoint
midpoint = (i + j) / 2;

// Recursive Calls
// Divided the Array into 2 SubArrays
mergeSort(array, i, midpoint, Temp);
mergeSort(array, midpoint + 1, j, Temp);
	
// Merge the SubArrays
Merge(array, i, j, midpoint, Temp);
}

////////////////////
// Merge Function //
////////////////////
void Merge(int values[], int i, int j, int midpoint, int Temp[])
{
int begin1 = i;
int end1 = midpoint;
int begin2 = midpoint + 1;
int end2 = j;
int index = i;

// Loop thru both SubArrays
for(; (begin1 <= end1) && (begin2 <= end2); index++)
   {
   // This copies the smallest of two values from SubArrays to Temp Array
   if(values[begin1] < values[begin2])
      {
      Temp[index] = values[begin1];
      begin1++;
      }
   else
      {
      Temp[index] = values[begin2];
      begin2++;
      }
   }
	
// Arranges the values in SubArray 1
for(; begin1 <= end1; begin1++, index++)
   Temp[index] = values[begin1];
	
// Arranges the values in SubArray 2
for(; begin2 <= end2; begin2++, index++)
   Temp[index] = values[begin2];
	
// Copies the values from the Temp Array to values Array
for(int k = i; k <= j; k++)
   values[k] = Temp[k];
}

////////////////////////////
// insertionSort Function //
////////////////////////////
void insertionSort(int values[], int size)
{
int key;

for(int j = 1; j < size; j++)
   {
   key = values[j];
   int i = j - 1;
   
   while((i >= 0) && (values[i] > key))
      {
      values[i+1] = values[i];
      i--;
      }

   values[i+1] = key;
   }
}

////////////////////////
// radixSort Function //
////////////////////////
void radixSort(int *_s, int *_t, int _n)
{
radix(0, _n, _s, _t);
radix(1, _n, _t, _s);
radix(2, _n, _s, _t);
radix(3, _n, _t, _s);
}

////////////////////
// radix Function //
////////////////////
void radix(int _b, int _n, int *_s, int *_d)
{
int count[256];
int index[256];
memset (count, 0, sizeof (count));
int i;
for(i = 0; i < _n; i++)
   count[((_s[i]) >> (_b * 8))&0xff]++;

index[0] = 0;
for(i = 1; i < 256; i++)
   index[i] = index[i-1] + count[i-1];
for(i = 0; i < _n; i++)
   _d[index[((_s[i]) >> (_b * 8))&0xff]++] = _s[i];
}

///////////////////////
// HeapSort Function //
///////////////////////
void HeapSort(int A[], int heapSize)
{
BuildHeap(A, heapSize);
for(int i=heapSize; i>1; --i)
   {
   int tmp = A[0];
   A[0] = A[i-1];
   A[i-1] = tmp;
   --heapSize;
   Heapify(A, 1, heapSize);
   }
}

////////////////////////
// BuildHeap Function //
////////////////////////
void BuildHeap(int A[], int heapSize)
{
for(int i=heapSize/2; i>0; --i)
   Heapify(A, i, heapSize);
}

//////////////////////
// Heapify Function //
//////////////////////
void Heapify(int A[], int i, int heapSize)
{
int l = 2 * i;
int r = 2 * i + 1;
int largest = 0;
if(l <= heapSize && A[l-1] > A[i-1])
   largest = l;
else
   largest = i;
if(r <= heapSize && A[r-1] > A[largest-1])
   largest = r;
if(largest != i)
   {
   int tmp = A[i-1];
   A[i-1] = A[largest-1];
   A[largest-1] = tmp;
   Heapify(A, largest, heapSize);
   }
}

////////////////////////////////////////////////////////
// Overloaded Insertion Sort Function for Bucket Sort //
////////////////////////////////////////////////////////
void insertionSort(list <float> & bucket)
{
if(bucket.size() == 1 || bucket.size() == 0)
   {
   return;
}
else
   {
   list <float>::iterator j = bucket.begin ();
   j++;
   for(; j != bucket.end(); j++)
      {
      float key = *j;
      list <float>::iterator k = j;
      k--;
      list <float>::iterator i = k;
      while(i != 0 && *i > key)
         {
         k = i;
         k++;
         *k = *i;
         i--;
         }
      k = i;
      k++;
      *k = key;
      } 
   }
}

//////////////////////////
// Bucket Sort Function //
//////////////////////////
float* BucketSort(float A[], int size)
{
int i = 0;
int index = 0;
list <float> *bucketData;
bucketData = new list <float> [size];
for(i = 0; i < size; i++)
   {
   index = (int)(A[i] *size);
   bucketData[index].push_back(A[i]);
   }
for(i = 0; i < size; i++)
   insertionSort(bucketData[i]);
list <float> concatList;
for(i = 0; i < size; i++)
   concatList.splice(concatList.end(), bucketData[i]);
list <float>::iterator concatListIterator = concatList.begin();
for(i = 0; i < size; i++)
   {
   A[i] = *concatListIterator;
   concatListIterator++;
   }
return A;
}

//////////////////////////////////////////////////////
// insertionSort Overloaded Function for BucketSort //
//////////////////////////////////////////////////////
void insertionSort(float values[], int size)
{
int key;

for(int j = 1; j < size; j++)
   {
   key = values[j];
   int i = j - 1;
   
   while((i >= 0) && (values[i] > key))
      {
      values[i+1] = values[i];
      i--;
      }

   values[i+1] = key;
   }
}

////////////////////////
// Quicksort Function //
////////////////////////
void Quicksort(int a[], int low, int high)
{
int q;
if(low < high)
   {
   q = Partition(a, low, high);
   Quicksort(a, low, q-1);
   Quicksort(a, q+1, high);
   }
}

///////////////////
// Swap Function //
///////////////////
void Swap(int a[], int one, int two)
{
int temp;
temp = a[one];
a[one] = a[two];
a[two] = temp;
}

////////////////////////
// Partition Function //
////////////////////////
int Partition( int a[], int low, int high)
{
int pivot, p_pos, i;
p_pos = low;
pivot = a[p_pos];
for(i=low+1;i<=high;i++)
   {
   if( a[i] < pivot )
      {
 	  p_pos++;
      Swap(a, p_pos, i);
      }
   }
Swap(a,low,p_pos);
return p_pos;
}

////////////////////////////
// Counting Sort Function //
////////////////////////////
void CountingSort(int A[], int B[], int k, int size)
{
int *C = new int[k];     // temp array
int i;

for(i=0; i<=k; i++)      // initialize C[] to be all 0's
   C[i] = 0;

for(i=0; i<size; i++)    // do the counting
   C[A[i]] = C[A[i]] +1;  // C[i] now has # of elements == to i

for(i=1; i<=k; i++)      // C[i] now has # of elements <= i
   C[i] = C[i] + C[i-1];

for(i=size-1; i>=0; i--) // build the sorted array
  {
  B[C[A[i]]-1] = A[i];
  C[A[i]] = C[A[i]] -1;
  }
}

///////////////////////////
// printResults Function //
///////////////////////////
void printResults(double totalTime, int title)
{
char* titles[] = {"Merge Sort", "Insertion Sort", "Radix Sort", "Heap Sort",
                  "Bucket Sort", "Quick Sort", "Counting Sort"};
cout << "The execution time for " << titles[title] << " is:: "  
     << setprecision(5) << setiosflags(ios::fixed|ios::showpoint) 
     << totalTime << " Seconds." << endl;
}

/////////////////////////////////////////////////////////////////////
// printToScreen Overloaded Function -- this is for debugging only //
/////////////////////////////////////////////////////////////////////
#ifdef DEBUGIT
void printToScreen(int values[], int size, int stepSize)
{
int columns = 0;
cout << endl << "DEBUG CODE::: " << endl;
for(int i = 0; i < size; i += stepSize)
   {
   cout << setw(6) << values[i];
   columns++;

   if(columns % 10 == 0)
      cout << endl;
   }
   cout << endl;
}

/////////////////////////////////////////////////////////////////////
// printToScreen Overloaded Function -- this is for debugging only //
/////////////////////////////////////////////////////////////////////
void printToScreen(float values[], int size, int stepSize)
{
int columns = 0;
cout << endl << "DEBUG CODE::: " << endl;
for(int i = 0; i < size; i += stepSize)
   {
   cout << setw(6) << setprecision(3) << setiosflags(ios::fixed|ios::showpoint) << values[i];
   columns++;

   if(columns % 10 == 0)
      cout << endl;
   }
   cout << endl;
}
#endif