/**
 * sort.c
 * Copyright (C) 2008 Markus Broeker
 *
 * Comparision of Sorting Algorithms
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#ifndef MAX
#define MAX 50000
#endif

unsigned long counter = 0;
unsigned long iters = 0;

int compare (int *a, int *b)
{
    iters++;
    if (*a > *b) {
        counter++;
        return 1;
    }
    return 0;
}

void swap (int *v, int i, int j)
{
    int old;

    if (i == j)
        return;

    old = v[i];

    v[i] = v[j];
    v[j] = old;
}

void statistic (char *func)
{
    printf ("%8s finished after %10lu swaps and %10lu Iterations.\n", func, counter, iters);
    counter = iters = 0;
}

/**
 * Laufzeitverhalten: n^2-n Durchläufe zum Sortieren von n Elementen...
 */
void lazysort (int *v, int n, int (*compare_func) (int *, int *))
{
    int i, j;

    for (i = 1; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (compare_func (&v[j], &v[i])) {
                swap (v, i, j);
            }
        }
    }
    statistic ("Lazy");
}

/**
 * Laufzeitverhalten: (1/2)*n^2-n Durchläufe zum Sortieren von n Elementen...
 */
void linearsort (int *v, int n, int (*compare) (int *, int *))
{
    int i, j;

    for (i = (n - 1); i > 0; i--) {
        for (j = 1; j <= i; j++) {
            if (compare (&v[j - 1], &v[j])) {
                swap (v, j - 1, j);
            }
        }
    }
    statistic ("Linear");
}

/**
 * Laufzeitverhalten: ~(1/{2|4})*n^2-n Durchläufe zum Sortieren...
 */
void bubblesort (int *v, int n, int (*compare) (int *, int *))
{
    int i;
    int swapped;

    do {
        swapped = 0;
        for (i = 1; i < n; i++) {
            if (compare (&v[i - 1], &v[i])) {
                swap (v, i, i - 1);
                swapped = 1;
            }
        }
        n--;
    } while (swapped && n >= 1);

    statistic ("Bubble");
}

static int divide (int *v, int left, int right)
{
    int i, j, pivot;

    i = left;
    j = right - 1;

    pivot = v[right];

    do {
        while (v[i] <= pivot && i < right) {
            iters++;
            i++;
        }
        while (v[j] >= pivot && j > left) {
            iters++;
            j--;
        }
        if (i < j) {
            counter++;
            swap (v, i, j);
        }

        if (v[i] > pivot) {
            counter++;
            swap (v, i, right);
        }
    } while (i < j);

    return i;
}

void quicksort (int *v, int left, int right)
{
    int divisor;

    if (left < right) {
        divisor = divide (v, left, right);
        quicksort (v, left, divisor - 1);
        quicksort (v, divisor + 1, right);
    }
}

int main (int argc, char **argv)
{
    int a[MAX];
    int b[MAX];
    int c[MAX];
    int d[MAX];
    int e[MAX];

    int i;

    srand (time (NULL));

    for (i = 0; i < MAX; i++) {
        a[i] = (int)((float)MAX * rand () / (RAND_MAX + 1.0));
    }

    memcpy (b, a, sizeof (a));
    memcpy (c, a, sizeof (a));
    memcpy (d, a, sizeof (a));
    memcpy (e, a, sizeof (a));

    lazysort (a, MAX, &compare);
    linearsort (b, MAX, &compare);
    bubblesort (c, MAX, &compare);

    quicksort (d, 0, MAX - 1);
    statistic ("mquick");

    qsort (e, MAX, sizeof (int), (void *)&compare);
    statistic ("gquick");

    printf ("PRESS <RETURN> to CONTINUE");
    while (getchar () != '\n');

    printf ("%6c %6c %6c %6c %6c\n----------------------------------\n", 'L', 'N', 'B', 'M', 'G');
    for (i = 0; i < MAX; i++)
        printf ("%6d %6d %6d %6d %6d\n", a[i], b[i], c[i], d[i], e[i]);

    return EXIT_SUCCESS;
}