/*
    sort.cpp
    CIS 150
    David Klick
    6/27/05

    Demonstration of various sorting algorithms.
*/

#include <iostream>
#include <cstdlib>
#include <ctime>
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);

int main(void) {
   srand(time(NULL));
   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";

}

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

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 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);
}

/*
   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
*/