diff --git a/sort.c b/sort.c new file mode 100644 --- /dev/null +++ b/sort.c @@ -0,0 +1,106 @@ +/** + * Comparision of Sorting Algorithms + * Copyright (C) 2008 Markus Broeker + */ + +#include +#include +#include +#include + +#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*(n-1) 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*(n-1) Durchläufe zum Sortieren von n Elementen... + */ +void bubblesort (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 ("Bubble"); +} + +int main (int argc, char **argv) +{ + int a[MAX]; + int b[MAX]; + int c[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)); + + lazysort (a, MAX, &compare); + bubblesort (b, MAX, &compare); + + qsort (c, MAX, sizeof (int), (void *)&compare); + statistic ("Quick"); + + printf ("PRESS to CONTINUE"); + while (getchar () != 10); + printf ("%2c %2c %2c\n--------\n", 'L', 'B', 'Q'); + + for (i = 0; i < MAX; i++) + printf ("%2d %2d %2d\n", a[i], b[i], c[i]); + + return 0; +}