qsort_analysis.cpp

#include <vector>
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <tictoc.h>
#include <assert.h>

using namespace std;

bool isSorted(const vector<int>& array) {
    for (int i=1; i<array.size(); i++)
        if (array[i] < array[i-1]) return false;
    return true;
}

void swap(int array[], int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

void quicksort1(int array[], int left, int right) {
#ifdef DEBUG
    static int counter = 0;
    counter++;
    printf("#%d quicksort1 with %d,%d\n", counter, left, right);
#endif
    if (left >= right) return;
    int pivot = left;
    int i = left+1, j = right;
    while (true) {
        while (i < j && array[i] <= array[pivot]) i++;
        while (array[j] > array[pivot]) j--;
        if (i >= j) break;
        swap(array, i, j);
    }
    swap(array, pivot, j);

    quicksort1(array, left, j-1);
    quicksort1(array, j+1, right);
}

void quicksort2(int array[], int left, int right) {
#ifdef DEBUG
    static int counter = 0;
    counter++;
    printf("#%d quicksort2 with %d,%d\n", counter, left, right);
#endif
    if (left >= right) return;
    int pivot = left;
    int i = left+1, j = right;
    while (true) {
        while (i < j && array[i] < array[pivot]) i++;
        while (array[j] > array[pivot]) j--;
        if (i >= j) break;
        swap(array, i++, j--);
    }
    swap(array, pivot, j);

    quicksort2(array, left, j-1);
    quicksort2(array, j+1, right);
    
}

int main(int argc, char** argv) {
	const int NUM_ELEMENTS = atoi(argv[1]);
    srand(time(NULL));
    vector<int> array(NUM_ELEMENTS);
    int NUM_KEYS = atoi(argv[2]);
    for (int i=0; i<NUM_ELEMENTS; i++)
        array[i] = rand()%NUM_KEYS;

    vector<int> array1(array), array2(array);
    tic();
    quicksort1(&array1[0], 0, NUM_ELEMENTS-1);
    toc();
    assert(isSorted(array1));
    tic();
    quicksort2(&array2[0], 0, NUM_ELEMENTS-1);
    toc();
    assert(isSorted(array2));

    return 0;
};