/**

 * Comparision of Sorting Algorithms

 * Copyright (C) 2008 Markus Broeker

 */

#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 = 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");

}

int main (int argc, char **argv)

{

    int a[MAX];

    int b[MAX];

    int c[MAX];

    int d[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));

    lazysort (a, MAX, &compare);

    linearsort (b, MAX, &compare);

    bubblesort (c, MAX, &compare);

    printf ("PRESS <RETURN> to CONTINUE");

    for (i = 0; i < MAX; i++)

    return EXIT_SUCCESS;

}