// quicksorter.cpp - implements QuickSorter
// cmc, 11/2/2013

#include "quicksorter.h"

// utility function to partition array segments for quicksort
void partition(double x[], int &i, int &j) {
    double pivot = x[(i + j) / 2]; // middle element is the pivot

    do {
        // scan i from left, then j from right
        while (x[i] < pivot) i++;   // note: i and j
        while (x[j] > pivot) j--;   // are reference parameters

        // swap if i and j haven't crossed yet
        if (i <= j) {
            double temp = x[i];
            x[i] = x[j];
            x[j] = temp;
            // and advance i and j to next elements
            i++;
            j--;
        }
    }while(i <= j);  // keep scanning until i and j cross
}

// recursive quicksort for double array
void quicksort(double x[], int left, int right) {
    int i, j;

    if (left < right) {
        i = left; j = right;
        partition(x, i, j);
        quicksort(x, left, j);
        quicksort(x, i, right);
    }
}

// first call just passes whole array to quicksort
void QuickSorter::sort(double x[], int n) {
    quicksort(x, 0, n-1);
}