/*
    testsort.cpp
    CIS 150
    David Klick
    6/24/08

    Demonstration of various sorting algorithms.
*/

#include <iostream>
#include <cstdlib>
#include <ctime>
using std::cin;
using std::cout;
using std::endl;

const int ARRAY_SIZE = 50000;

void copyArray(int*, int*, int);
bool isSorted(int*, int);
void bubbleSort(int*, int);
void mySort(int*, int);
void woldSort(int*, int);
void insertionSort(int*, int);
void selectionSort(int*, int);
void shellSort(int*, int);
void mergeSort(int*, int);
void m_sort(int*, int*, int, int);
void merge(int*, int*, int, int, int);
void heapSort(int*, int);
void siftDown(int*, int, int);
void quickSort(int*, int);
void q_sort(int*, int, int);
void cont();

int main() {
   srand(time(0));
   clock_t startTime, stopTime;
   double elapsedTime;
   const int RANGE = 1000000;
   int work[ARRAY_SIZE];
   int hold[ARRAY_SIZE];

   // create an array of random integers
   for (int i=0; i<ARRAY_SIZE; i++) {
      hold[i] = rand() % RANGE;
   }

   // copy holding array to working array and do bubble sort
   copyArray(hold, work, ARRAY_SIZE);
   if (isSorted(work, ARRAY_SIZE)) cout << "Error: array sorted before sort\n";
   cout << "Sorting work array using bubble sort ";
   startTime = clock();
   bubbleSort(work, ARRAY_SIZE);
   stopTime = clock();
   elapsedTime = difftime(stopTime, startTime);
   if (!isSorted(work, ARRAY_SIZE)) cout << "- bubble sort failed!\n";
   else cout << "- elapsed time: " << elapsedTime << "ms\n";

   // copy holding array to working array and do my sort
   copyArray(hold, work, ARRAY_SIZE);
   if (isSorted(work, ARRAY_SIZE)) cout << "Error: array sorted before sort\n";
   cout << "Sorting work array using my sort ";
   startTime = clock();
   mySort(work, ARRAY_SIZE);
   stopTime = clock();
   elapsedTime = difftime(stopTime, startTime);
   if (!isSorted(work, ARRAY_SIZE)) cout << "- my sort failed!\n";
   else cout << "- elapsed time: " << elapsedTime << "ms\n";

   // copy holding array to working array and do Jermey Wold's sort
   copyArray(hold, work, ARRAY_SIZE);
   if (isSorted(work, ARRAY_SIZE)) cout << "Error: array sorted before sort\n";
   cout << "Sorting work array using Wold sort ";
   startTime = clock();
   woldSort(work, ARRAY_SIZE);
   stopTime = clock();
   elapsedTime = difftime(stopTime, startTime);
   if (!isSorted(work, ARRAY_SIZE)) cout << "- Wold sort failed!\n";
   else cout << "- elapsed time: " << elapsedTime << "ms\n";

   // copy holding array to working array and do selection sort
   copyArray(hold, work, ARRAY_SIZE);
   if (isSorted(work, ARRAY_SIZE)) cout << "Error: array sorted before sort\n";
   cout << "Sorting work array using selection sort ";
   startTime = clock();
   selectionSort(work, ARRAY_SIZE);
   stopTime = clock();
   elapsedTime = difftime(stopTime, startTime);
   if (!isSorted(work, ARRAY_SIZE)) cout << "- selection sort failed!\n";
   else cout << "- elapsed time: " << elapsedTime << "ms\n";

   // copy holding array to working array and do insertion sort
   copyArray(hold, work, ARRAY_SIZE);
   if (isSorted(work, ARRAY_SIZE)) cout << "Error: array sorted before sort\n";
   cout << "Sorting work array using insertion sort ";
   startTime = clock();
   insertionSort(work, ARRAY_SIZE);
   stopTime = clock();
   elapsedTime = difftime(stopTime, startTime);
   if (!isSorted(work, ARRAY_SIZE)) cout << "- insertion sort failed!\n";
   else cout << "- elapsed time: " << elapsedTime << "ms\n";

   // copy holding array to working array and do shell sort
   copyArray(hold, work, ARRAY_SIZE);
   if (isSorted(work, ARRAY_SIZE)) cout << "Error: array sorted before sort\n";
   cout << "Sorting work array using shell sort ";
   startTime = clock();
   shellSort(work, ARRAY_SIZE);
   stopTime = clock();
   elapsedTime = difftime(stopTime, startTime);
   if (!isSorted(work, ARRAY_SIZE)) cout << "- shell sort failed!\n";
   else cout << "- elapsed time: " << elapsedTime << "ms\n";

   // copy holding array to working array and do merge sort
   copyArray(hold, work, ARRAY_SIZE);
   if (isSorted(work, ARRAY_SIZE)) cout << "Error: array sorted before sort\n";
   cout << "Sorting work array using merge sort ";
   startTime = clock();
   mergeSort(work, ARRAY_SIZE);
   stopTime = clock();
   elapsedTime = difftime(stopTime, startTime);
   if (!isSorted(work, ARRAY_SIZE)) cout << "- merge sort failed!\n";
   else cout << "- elapsed time: " << elapsedTime << "ms\n";

   // copy holding array to working array and do heap sort
   copyArray(hold, work, ARRAY_SIZE);
   if (isSorted(work, ARRAY_SIZE)) cout << "Error: array sorted before sort\n";
   cout << "Sorting work array using heap sort ";
   startTime = clock();
   heapSort(work, ARRAY_SIZE);
   stopTime = clock();
   elapsedTime = difftime(stopTime, startTime);
   if (!isSorted(work, ARRAY_SIZE)) cout << "- heap sort failed!\n";
   else cout << "- elapsed time: " << elapsedTime << "ms\n";

   // copy holding array to working array and do quick sort
   copyArray(hold, work, ARRAY_SIZE);
   if (isSorted(work, ARRAY_SIZE)) cout << "Error: array sorted before sort\n";
   cout << "Sorting work array using quick sort ";
   startTime = clock();
   quickSort(work, ARRAY_SIZE);
   stopTime = clock();
   elapsedTime = difftime(stopTime, startTime);
   if (!isSorted(work, ARRAY_SIZE)) cout << "- quick sort failed!\n";
   else cout << "- elapsed time: " << elapsedTime << "ms\n";

   cont();
   return 0;
}

/*
   void copyArray(int from[], int to[], int len);
   
   Arguments:
      int from[]: array of integers to copy
      int to[]: array to copy integers to
      int len: number of elements in from[] array
         Note: to[] array must be same size or larger

   Returns: nothing

   Copies the values in the from[] array into the to[] array.
*/
void copyArray(int from[], int to[], int len) {
   for (int i=0; i<len; i++) to[i] = from[i];
}

/*
   bool isSorted(int a[], int len);
   
   Arguments:
      int a[]: array of integers to be checked
      int len: number of elements in array

   Returns: True if array is in ascending sorted order,
      else false.

   Checks whether the array passed in is in sorted order.
   Returns true if it is, else false.
*/
bool isSorted(int a[], int len) {
   for (int i=0; i<len-1; i++) {
      if (a[i] > a[i+1]) return false;
   }
   return true;
}

/*
   void mySort(int a[], int len);
   
   Arguments:
      int a[]: array of integers to be sorted
      int len: number of elements in array

   Returns: nothing (but a side effect is that the array
      passed in is put into ascending sorted order)

   Sorts the integer array a[] into ascending order.
   This is a very inefficient sort and should not be used
   for most real-world problems.
*/
void mySort(int a[], int len) {
   int i, j, temp;
   for (i=0; i<len-1; i++) {
      for (j = i+1; j<len; j++) {
         if (a[i] > a[j]) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
         }
      }
   }
}

/*
   void bubbleSort(int a[], int len);
   
   Arguments:
      int a[]: array of integers to be sorted
      int len: number of elements in array

   Returns: nothing (but a side effect is that the array
      passed in is put into ascending sorted order)

   Sorts the integer array a[] into ascending order.
   This is an inefficient sort and should not be used
   for most real-world problems.
*/
void bubbleSort(int a[], int len) {
   int i, j, temp;
   for (i=len-1; i>=0; i--) {
      for (j = 1; j <= i; j++) {
         if (a[j-1] > a[j]) {
            temp = a[j-1];
            a[j-1] = a[j];
            a[j] = temp;
         }
      }
   }
}

/*
   void woldSort(int a[], int len);
   
   Arguments:
      int a[]: array of integers to be sorted
      int len: number of elements in array

   Returns: nothing (but a side effect is that the array
      passed in is put into ascending sorted order)

   Sorts the integer array a[] into ascending order.
   This is an inefficient sort and should not be used
   for most real-world problems.
*/
void woldSort(int a[], int len) {
   int i, j, k, temp;
   for (i=0; i<len-1; i++) {
      for (j=i+1; j<len; j++) {
      if (a[i] > a[j]) {
         temp = a[j];
         for (k=j; k>i; k--) a[k] = a[k-1];
            a[i] = temp;
         }
      }
   }
}

/*
   void selectionSort(int a[], int len);
   
   Arguments:
      int a[]: array of integers to be sorted
      int len: number of elements in array

   Returns: nothing (but a side effect is that the array
      passed in is put into ascending sorted order)

   Sorts the integer array a[] into ascending order.
   This is an inefficient sort.
*/
void selectionSort(int a[], int len) {
   int i, j, min, temp;
   for (i=0; i<len-1; i++) {
      min = i;
      for (j=i+1; j<len; j++) {
         if (a[j] < a[min]) min = j;
      }
      temp = a[i];
      a[i] = a[min];
      a[min] = temp;
   }
}

/*
   void insertionSort(int a[], int len);
   
   Arguments:
      int a[]: array of integers to be sorted
      int len: number of elements in array

   Returns: nothing (but a side effect is that the array
      passed in is put into ascending sorted order)

   Sorts the integer array a[] into ascending order.
   This is a somewhat inefficient sort.
*/
void insertionSort(int a[], int len) {
   int i, j, temp;
   for (i=1; i<len; i++) {
      temp = a[i];
      j = i;
      while ((j>0) && (a[j-1] > temp)) {
         a[j] = a[j-1];
         j--;
      }
      a[j] = temp;
   }
}

/*
   void shellSort(int a[], int len);
   
   Arguments:
      int a[]: array of integers to be sorted
      int len: number of elements in array

   Returns: nothing (but a side effect is that the array
      passed in is put into ascending sorted order)

   Sorts the integer array a[] into ascending order.
   This is a somewhat inefficient sort.
*/
void shellSort(int a[], int len) {
   int i, j, incr, temp;
   incr = 3;
   while (incr > 0) {
      for (i=0; i<len; i++) {
         j = i;
         temp = a[i];
         while ((j >= incr) && (a[j-incr] > temp)) {
            a[j] = a[j-incr];
            j -= incr;
         }
         a[j] = temp;
      }
      if (incr/2 != 0) incr /= 2;
      else if (incr == 1) incr = 0;
      else incr = 1;
   }
}

/*
   void mergeSort(int a[], int len);
   
   Arguments:
      int a[]: array of integers to be sorted
      int len: number of elements in array

   Returns: nothing (but a side effect is that the array
      passed in is put into ascending sorted order)

   Requires:
      void m_sort(int*, int*, int, int);
      void merge(int*, int*, int, int, int);

   Sorts the integer array a[] into ascending order.
   This sort mimics a sort often used in the past with
   sequential I/O devices. It can be a very efficient
   sort depending on the previous ordering of the data.
*/
void mergeSort(int a[], int len) {
   int *tmp = new int[len];
   m_sort(a, tmp, 0, len-1);
   delete[] tmp;
}

/*
   void m_sort(int a[], int tmp[], int left, int right);
   
   Arguments:
      int a[]: array of integers to be sorted
      int tmp[]: an array used as a scratch area for sorting; must
         be at least as large as a[]
      int left: the position of the leftmost array item to be sorted
      int right: the position of the rightmost array item to be sorted

   Returns: nothing (but a side effect is that the range specified
      in the array passed in is put into ascending sorted order)

   Requires:
      void merge(int*, int*, int, int, int);

   This is a recursive sort which divides an array into two sections,
   sorts each section, and then merges the results.
*/
void m_sort(int a[], int tmp[], int left, int right) {
   int mid;
   if (right > left) {
      mid = (right + left) / 2;
      m_sort(a, tmp, left, mid);
      m_sort(a, tmp, mid+1, right);
      merge(a, tmp, left, mid+1, right);
   }
}

/*
   void merge(int a[], int tmp[], int left, int mid, int right);
   
   Arguments:
      int a[]: array of integers to be sorted
      int tmp[]: an array used as a scratch area for merging; must
         be at least as large as a[]
      int left: the leftmost position of the first sorted sequence
      int mid: the leftmost position of the second sorted sequence
      int right: the position of the end of the second sorted sequence

   Returns: nothing (but a side effect is that the range specified
      in the array passed in is put into ascending sorted order)

   This function merges two sections of an array which are each in sorted
   order into a single sorted section.
*/
void merge(int a[], int tmp[], int left, int mid, int right) {
   int i, left_end, num_elements, tmp_pos;
   left_end = mid - 1;
   tmp_pos = left;
   num_elements = right - left + 1;

   while ((left <= left_end) && (mid <= right)) {
      if (a[left] <= a[mid]) tmp[tmp_pos++] = a[left++];
      else tmp[tmp_pos++] = a[mid++];
   }

   while (left <= left_end) tmp[tmp_pos++] = a[left++];
   while (mid <= right) tmp[tmp_pos++] = a[mid++];

   for (i=0; i < num_elements; i++) {
      a[right] = tmp[right];
      right--;
   }
}

/*
   void heapSort(int a[], int len);
   
   Arguments:
      int a[]: array of integers to be sorted
      int len: number of elements in array

   Returns: nothing (but a side effect is that the array
      passed in is put into ascending sorted order)

   Requires:
      void siftDown(int*, int, int);

   Sorts the integer array a[] into ascending order.
   This sort is very efficient.
*/
void heapSort(int a[], int len) {
   for (int i=len/2; i>0; i--) siftDown(a, i, len);
   do {
      int tmp = a[0];
      a[0] = a[len-1];
      a[len-1] = tmp;
      len--;
      siftDown(a, 1, len);
   } while (len>1);
}

/*
   void siftDown(int a[], int k, int bottom);
   
   Arguments:
      int a[]: array of integers to be heapified
      int k: number of elements in array still being heapified
      int bottom: number of elements in array

   Returns: nothing (but a side effect is that the specified
      range of the array passed in is put into proper heap order)

   Puts the range of the array specified into proper heap order.
*/
void siftDown(int a[], int k, int bottom) {
   int tmp = a[k-1];
   while (k <= bottom/2) {
      int j = k + k;
      if ((j < bottom) && (a[j-1]<a[j])) j++;
      if (tmp >= a[j-1]) break;
      else {
         a[k-1] = a[j-1];
         k = j;
      }
   }
   a[k-1] = tmp;
}

/*
   void quickSort(int a[], int len);
   
   Arguments:
      int a[]: array of integers to be sorted
      int len: number of elements in array

   Returns: nothing (but a side effect is that the array
      passed in is put into ascending sorted order)

   Requires:
      void q_sort(int*, int, int);

   Sorts the integer array a[] into ascending order.
   This sort is very efficient.
*/
void quickSort(int a[], int len) {
   q_sort(a, 0, len-1);
}

/*
   void q_sort(int a[], int left. int right);
   
   Arguments:
      int a[]: array of integers to be sorted
      int left: leftmost position of range to sort
      int right: rightmost position of range to sort

   Returns: nothing (but a side effect is that the array
      passed in is put into ascending sorted order)

   Sorts the integer array a[] into ascending order.
   This sort is very efficient.
*/
void q_sort(int a[], int left, int right) {
   int pivot, l_hold, r_hold;
   l_hold = left;
   r_hold = right;
   pivot = a[left];
   while (left < right) {
      while ((a[right] >= pivot) && (left < right)) right--;
      if (left != right) a[left++] = a[right];
      while ((a[left] <= pivot) && (left < right)) left++;
      if (left != right) a[right--] = a[left];
   }
   a[left] = pivot;
   pivot = left;
   left = l_hold;
   right = r_hold;
   if (left < pivot) q_sort(a, left, pivot-1);
   if (right > pivot) q_sort(a, pivot+1, right);
}

/*
   void cont();
   
   Arguments: none
   
   Returns: nothing
   
   Clears input buffer and pauses waiting for user 
   to press Enter.
*/
void cont() {
   if (cin.rdbuf()->sungetc() != -1 && cin.get() != '\n') cin.ignore(80,'\n');
   cout << "Press enter to continue...";
   cin.get();
}

/*
   Sample output:
   
   Sorting work array using bubble sort - elapsed time: 16953ms
   Sorting work array using my sort - elapsed time: 14657ms
   Sorting work array using Wold sort - elapsed time: 8734ms
   Sorting work array using selection sort - elapsed time: 5406ms
   Sorting work array using insertion sort - elapsed time: 3641ms
   Sorting work array using shell sort - elapsed time: 1656ms
   Sorting work array using merge sort - elapsed time: 16ms
   Sorting work array using heap sort - elapsed time: 15ms
   Sorting work array using quick sort - elapsed time: 16ms
*/