Quicksort - randomized

#include "stdio_wrap.h"
#include "stdlib_wrap.h"
#include "time.h"

int rand_n(int);
int rand_range(int, int);
void swap(int [], int, int);

void KR_rand_qsort(int [], int, int);
void KR_qsort(int [], int, int);

void inter_sort(int [], int);

void alg_rand_qsort(int a[], int lo, int hi);
void alg_qsort(int a[], int lo, int hi);

void count_itr(char *, int[], int, void (*)(int[], int, int));

// Used to count the the iterations perfomed when sorting.
int itr_perf = 0;


#define INPUT "i.txt"
#define SORTED "sorted.txt"
#define CHECK "result.txt"

int main()
{
    /*
      int test[] = {
      10, 9, 34, 14, 8, 6, 39, 1, 4, 34, 431, 43, 98, 35, 89, 349, 956, 5, 3, 43
      };
      //alg_rand_qsort(test, 0, NELEMS(test) - 1);
      //fprintarr(stdout, "%d ", test, NELEMS(test));
      */

    int arr[100000];
    size_t n = 100000;
    FILE *input, *out;

    file_isEmpty_(INPUT, return 0); input = ec_fopen(INPUT, "r");
    freadarr(input, "%d", arr, n);
    fclose(input);

    count_itr("simple k&r", arr, n, KR_qsort);
    count_itr("randomized k&r", arr, n, KR_rand_qsort);
    out = ec_fopen(SORTED, "w"); fprintarr(out, "%d ", arr, n); fclose(out);

    count_itr("simple v2", arr, n, alg_qsort);
    count_itr("randomized v2", arr, n, alg_rand_qsort);

    out = ec_fopen(CHECK, "w"); fprintarr(out, "%d ", arr, n); fclose(out);

    /* Verify. */
    FILE *verf, *res;

    verf = ec_fopen(SORTED, "r");
    res = ec_fopen(CHECK, "r");

    int a, b;
    forIn(i, 0, n) {
        fscanf(verf, "%d", &a);
        fscanf(res, "%d", &b);
        if (a != b) {
            printf("%d: %d != %d\n", i, a, b);
            exit(-1);
        }
    }
    fclose(verf); fclose(res);

    puts("[OK]");
    return 0;
}

void count_itr(char *qsort_name, int arr[], int n, void (*qsort_fn)(int arr[], int lo, int hi))
{
    itr_perf = 0;
    (*qsort_fn)(arr, 0, n - 1);
    printf("%s: %d\n", qsort_name, itr_perf);
}


void alg_rand_qsort(int a[], int lo, int hi)
{
    if (hi <= lo) {
        return;
    }

    swap(a, lo, rand_range(lo, hi)); // ++

    int key = a[lo], last = lo, rest = hi;

    while (last < rest)
    {
        //if (a[i] < key) ++last; (skip)
        if (a[last + 1] > key) {
            while (a[rest] > key && last < rest) {
                rest--;     ++itr_perf;
            }

            if (last < rest) {
                swap(a, ++last, rest--);
            }
        }
        else { ++last; ++itr_perf; }
    } // Now a[lo..last] < key < a[rest+1..hi].

    swap(a, lo, last); // Place pivot
    alg_rand_qsort(a, lo, last - 1);
    alg_rand_qsort(a, rest + 1, hi);
}


void alg_qsort(int a[], int lo, int hi)
{
    if (hi <= lo) {
        return;
    }

    int key = a[lo], last = lo, rest = hi;

    while (last < rest)
    {
        //if (a[i] < key) ++last; (skip)
        if (a[last + 1] > key) {
            while (a[rest] > key && last < rest) {
                ++itr_perf;
                rest--;
            }

            if (last < rest) {
                swap(a, ++last, rest--);
            }
        }
        else { ++last; ++itr_perf; }
    } // Now a[lo..last] < key < a[rest+1..hi].

    swap(a, lo, last); // Place pivot
    alg_qsort(a, lo, last - 1);
    alg_qsort(a, rest + 1, hi);
}



void KR_rand_qsort(int arr[], int left, int right)
{
    int last, mid = (left + right) / 2;

    if (left >= right) {
        return;
    }

    swap(arr, mid, rand_range(left, right)); // ++

    swap(arr, left, mid); /* move partition elem */

    last = left;
    for (int i = left + 1; i <= right; ++i) { /* partition */
        if (arr[i] < arr[left]) {
            swap(arr, ++last, i);
        }
        ++itr_perf;
    }

    swap(arr, left, last); /* place partition elem */
    KR_rand_qsort(arr, left, last - 1);
    KR_rand_qsort(arr, last + 1, right);
}


void KR_qsort(int v[], int left, int right)
{
    int last, mid = (left + right) / 2;

    if (left >= right)
        return;

    swap(v, left, mid); /* move partition elem */

    last = left;
    for (int i = left + 1; i <= right; i++) { /* partition */
        if (v[i] < v[left]) {
            swap(v, ++last, i);
        }
        ++itr_perf;
    }

    swap(v, left, last); /* place partition elem */
    KR_qsort(v, left, last - 1);
    KR_qsort(v, last + 1, right);
}


/* Returns a number from [l, r]. */
int rand_range(int l, int r)
{
    int rand = rand_n(r - l);

    return (rand < l) ? l + rand : rand;
}

/* Returns a random number form [0, n]. */
int rand_n(int n)
{
    static bool init;

    if (!init) {
        srand((unsigned int) time(NULL));
    }

    return rand() % (n + 1);
}

/* swap: interchange arr[i] and arr[j] */
void swap(int arr[], int i, int j)
{
    int temp;
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}