median_shuffled.cpp

#include <stdlib.h>

int     *val;                            /* item values */
int     ncmp;                            /* number of comparisons */
int     nsolid;                          /* number of solid items */
int     candidate;                       /* pivot candidate */
int     gas;                             /* gas value */

#define freeze(x) val[x] = nsolid++

int cmp(const void *px, const void *py){ /* per C standard */
    const int x = *(const int*)px;
    const int y = *(const int*)py;

    ncmp++;

    if (val[x]==gas && val[y]==gas){
        if (x == candidate) freeze(x);
        else freeze(y);
    }

    if (val[x] == gas) candidate = x;
    else if(val[y] == gas) candidate = y;

    return val[x] - val[y];          /* only the sign matters */
}

struct Compare {
    bool operator () (int a, int b){
        return cmp(&a, &b) < 0;
    }
};

#include <algorithm>

void quicksort_with_median(int *a, int *b){
    int n = b - a;
    if (n <= 1) return;
    int *median = a + n/2;
    std::nth_element(a, median, b, Compare());
    quicksort_with_median(a, median);
    quicksort_with_median(median + 1, b);
}

int antiqsort(int n, int *a, int use_qsort){
    int i;
    int *ptr = (int*)malloc(n*sizeof(*ptr));

    val = a;
    gas = n - 1;

    nsolid = ncmp = candidate = 0;

    for (i=0; i<n; i++){
        ptr[i] = i;
        val[i] = gas;
    }

    if (use_qsort){
        qsort(ptr, n, sizeof(*ptr), cmp);
    }else{
        quicksort_with_median(ptr, ptr + n);
    }

    free(ptr);
    return ncmp;
}

#include <stdio.h>
#include <random>

void shuffle(int *a, int n){
    std::random_device rd;
    std::mt19937 gen(rd());
    std::shuffle(a, a + n, gen);
}

int main(){
    printf("n, qsort, quicksort with median\n");
    for (int n = 0; n <= 5000; n += 100){
        int *a = (int*)malloc(n*sizeof(*a));
        for (int i = 0; i < n; i++) a[i] = i;
        shuffle(a, n);
        int n_qsort     = antiqsort(n, a, 1);
        shuffle(a, n);
        int n_quicksort = antiqsort(n, a, 0);
        printf("%i, %i, %i\n", n, n_qsort, n_quicksort);
        free(a);
    }
    return 0;
}