/*
Authors:Travis Gadberry
	Patrick Hesser
	Chris Ladewig
Date:	9 Feb 05
Updated:16 Feb 05
File:	QuickSort.cpp
*/


#ifndef QUICKSORT_H
#define QUICKSORT_H
  #include "QuickSort.h"
#endif

QuickSort::
QuickSort() {
  n = 1;
  A = new int[n];
  A[0] = 0;
  sorted = true;
}

QuickSort::
QuickSort(int * newArray, int N) {
  n = N;
  A = new int[n];
  for(int i=0; i<n; i++)
    A[i] = newArray[i];
  sorted = false;
  resetIncrements();
}

QuickSort::
~QuickSort() {
  delete(A);
}

int *
QuickSort::
getArray() {
  return A;
}

int
QuickSort::
getN() {
  return n;
}

bool
QuickSort::
getSorted() {
  return sorted;
}

double
QuickSort::
getTime() {
  return time;
}

int
QuickSort::
getIncrements() {
  return increments;
}

void
QuickSort::
setArray(int * newArray) {
  delete(A);
  n = sizeof(newArray);
  A = new int[n];
  sorted = false;
}

void
QuickSort::
sort() {
  clock_t t1, t2;
  t1 = clock();

  quicksort(A, 0, n-1);

  t2 = clock();
  time = (t2 - t1)/CLOCKS_PER_SEC;
}

void
QuickSort::
quicksort(int * list, int i, int n) {
  int p;

  if(increments++, i < n) {
    p = partition(list, i, n);  /* p is the list pivot position */
    quicksort(list, i, p-1);
    quicksort(list, p+1, n);
  }
}

int
QuickSort::
partition(int * list, int i, int j) {
  int middle=(i+j)/2;            /* middle as the pivot       */

  int pivot=list[middle];
  list[middle]=list[i];
  list[i]=pivot;

  int p=i;

  for(int k=i+1; k<=j; k++)
    if(increments++, list[k]<pivot) {          /* elements less than pivot  */
      int temp=list[++p];        /* replaced by list[++p]     */
      list[p]=list[k];
      list[k]=temp;
    }

  int temp=list[i];              /* pivot in list[p]          */
  list[i]=list[p];
  list[p]=temp;

  return p;                      /* return pivot position     */
}


void
QuickSort::
setN(int newN) {
  n = newN;
}

void
QuickSort::
setSorted(bool newSorted) {
  sorted = newSorted;
}

void
QuickSort::
resetTime() {
  time = 0.0;
}

void
QuickSort::
resetIncrements() {
  increments = 0;
}