/*
    sort.cpp
    CIS 250
    David Klick
    1/31/05
    revised 11/21/10

    Demonstration of various sorting algorithms.
*/

#include <iostream>
#include <cstdlib>
#include <sys/time.h>
#include <time.h>
#include <limits.h>
using std::cout;
using std::endl;

int ARRAY_SIZE = 100000;

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 quickSort2(int*, int);
void q_sort2(int*, int, int);

int main(int argc, char* argv[]) {
   if (argc > 1) ARRAY_SIZE = atoi(argv[1]);
   cout << "Array size: " << ARRAY_SIZE << '\n';

   long elapsedTime;
   srand(time(NULL));
   timeval startTime, stopTime;
   static struct timezone tz;
   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 ";
   gettimeofday(&startTime, &tz);
   bubbleSort(work, ARRAY_SIZE);
   gettimeofday(&stopTime, &tz);
   elapsedTime = (stopTime.tv_sec - startTime.tv_sec) * 1000000
      + (stopTime.tv_usec - startTime.tv_usec);
   if (!isSorted(work, ARRAY_SIZE)) cout << "- bubble sort failed!\n";
   else cout << "- elapsed time: " << elapsedTime << "us\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 ";
   gettimeofday(&startTime, &tz);
   mySort(work, ARRAY_SIZE);
   gettimeofday(&stopTime, &tz);
   elapsedTime = (stopTime.tv_sec - startTime.tv_sec) * 1000000
      + (stopTime.tv_usec - startTime.tv_usec);
   if (!isSorted(work, ARRAY_SIZE)) cout << "- my sort failed!\n";
   else cout << "- elapsed time: " << elapsedTime << "us\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 ";
   gettimeofday(&startTime, &tz);
   woldSort(work, ARRAY_SIZE);
   gettimeofday(&stopTime, &tz);
   elapsedTime = (stopTime.tv_sec - startTime.tv_sec) * 1000000
      + (stopTime.tv_usec - startTime.tv_usec);
   if (!isSorted(work, ARRAY_SIZE)) cout << "- Wold sort failed!\n";
   else cout << "- elapsed time: " << elapsedTime << "us\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 ";
   gettimeofday(&startTime, &tz);
   selectionSort(work, ARRAY_SIZE);
   gettimeofday(&stopTime, &tz);
   elapsedTime = (stopTime.tv_sec - startTime.tv_sec) * 1000000
      + (stopTime.tv_usec - startTime.tv_usec);
   if (!isSorted(work, ARRAY_SIZE)) cout << "- selection sort failed!\n";
   else cout << "- elapsed time: " << elapsedTime << "us\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 ";
   gettimeofday(&startTime, &tz);
   insertionSort(work, ARRAY_SIZE);
   gettimeofday(&stopTime, &tz);
   elapsedTime = (stopTime.tv_sec - startTime.tv_sec) * 1000000
      + (stopTime.tv_usec - startTime.tv_usec);
   if (!isSorted(work, ARRAY_SIZE)) cout << "- insertion sort failed!\n";
   else cout << "- elapsed time: " << elapsedTime << "us\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 ";
   gettimeofday(&startTime, &tz);
   shellSort(work, ARRAY_SIZE);
   gettimeofday(&stopTime, &tz);
   elapsedTime = (stopTime.tv_sec - startTime.tv_sec) * 1000000
      + (stopTime.tv_usec - startTime.tv_usec);
   if (!isSorted(work, ARRAY_SIZE)) cout << "- shell sort failed!\n";
   else cout << "- elapsed time: " << elapsedTime << "us\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 ";
   gettimeofday(&startTime, &tz);
   mergeSort(work, ARRAY_SIZE);
   gettimeofday(&stopTime, &tz);
   elapsedTime = (stopTime.tv_sec - startTime.tv_sec) * 1000000
      + (stopTime.tv_usec - startTime.tv_usec);
   if (!isSorted(work, ARRAY_SIZE)) cout << "- merge sort failed!\n";
   else cout << "- elapsed time: " << elapsedTime << "us\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 ";
   gettimeofday(&startTime, &tz);
   heapSort(work, ARRAY_SIZE);
   gettimeofday(&stopTime, &tz);
   elapsedTime = (stopTime.tv_sec - startTime.tv_sec) * 1000000
      + (stopTime.tv_usec - startTime.tv_usec);
   if (!isSorted(work, ARRAY_SIZE)) cout << "- heap sort failed!\n";
   else cout << "- elapsed time: " << elapsedTime << "us\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 ";
   gettimeofday(&startTime, &tz);
   quickSort(work, ARRAY_SIZE);
   gettimeofday(&stopTime, &tz);
   elapsedTime = (stopTime.tv_sec - startTime.tv_sec) * 1000000
      + (stopTime.tv_usec - startTime.tv_usec);
   if (!isSorted(work, ARRAY_SIZE)) cout << "- quick sort failed!\n";
   else cout << "- elapsed time: " << elapsedTime << "us\n";

   // copy holding array to working array and do quick sort 2
   copyArray(hold, work, ARRAY_SIZE);
   if (isSorted(work, ARRAY_SIZE)) cout << "Error: array sorted before sort\n";
   cout << "Sorting work array using quick sort 2 ";
   gettimeofday(&startTime, &tz);
   quickSort2(work, ARRAY_SIZE);
   gettimeofday(&stopTime, &tz);
   elapsedTime = (stopTime.tv_sec - startTime.tv_sec) * 1000000
      + (stopTime.tv_usec - startTime.tv_usec);
   if (!isSorted(work, ARRAY_SIZE)) cout << "- quick sort 2 failed!\n";
   else cout << "- elapsed time: " << elapsedTime << "us\n";
}

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) {
   for (int i=0; i<len-1; i++) {
      if (a[i] > a[i+1]) return false;
   }
   return true;
}

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) {
   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) {
   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) {
   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) {
   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) {
   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) {
   int tmp[len];
   m_sort(a, tmp, 0, len-1);
}

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) {
   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) {
   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) {
   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) {
   q_sort(a, 0, len-1);
}

void q_sort(int a[], int left, int right) {
   int pivotNdx, l_hold = left, r_hold = right;
   int 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;
   pivotNdx = left;
   left = l_hold;
   right = r_hold;
   if (left < pivotNdx) q_sort(a, left, pivotNdx-1);
   if (right > pivotNdx) q_sort(a, pivotNdx+1, right);
}

void quickSort2(int a[], int len) {
   q_sort2(a, 0, len-1);
}

void q_sort2(int a[], int left, int right) {
   if (right-left < 7) { insertionSort(a+left , right-left+1); return; }
   int pivotNdx, l_hold = left, r_hold = right;
   int 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;
   pivotNdx = left;
   left = l_hold;
   right = r_hold;
   if (left < pivotNdx) q_sort2(a, left, pivotNdx-1);
   if (right > pivotNdx) q_sort2(a, pivotNdx+1, right);
}

/*
   Example output:
   
   Array size: 100000
   Sorting work array using bubble sort - elapsed time: 55601917us
   Sorting work array using my sort - elapsed time: 55000546us
   Sorting work array using Wold sort - elapsed time: 32083126us
   Sorting work array using selection sort - elapsed time: 16975082us
   Sorting work array using insertion sort - elapsed time: 14584673us
   Sorting work array using shell sort - elapsed time: 5871250us
   Sorting work array using merge sort - elapsed time: 36676us
   Sorting work array using heap sort - elapsed time: 29243us
   Sorting work array using quick sort - elapsed time: 21331us
   Sorting work array using quick sort 2 - elapsed time: 19103us
*/