--- a/Makefile
+++ b/Makefile
@@ -41,7 +41,8 @@
prog_limit \
connection \
copy \
- function_pointers
+ function_pointers \
+ sort
.SUFFIXES: .c .cc .asm
@@ -225,6 +226,10 @@
@echo Linking $< ...
@$(CC) -o $@ $<
+sort: sort.o
+ @echo Linking $< ...
+ @$(CC) -o $@ $<
+
.PHONY: clean uninstall
clean:
new file mode 100644
--- /dev/null
+++ b/sort.c
@@ -0,0 +1,106 @@
+/**
+ * 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*(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 <RETURN> 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;
+}