# HG changeset patch
# User Markus Bröker <mbroeker@largo.dyndns.tv>
# Date 1229187497 -3600
# Node ID 6cf883f9c506688ba3134f1943f33c73f38760b4
# Parent  9cdad6c45b47f40d1f75b26c7544c7413f670354
sort demo added

committer: Markus Bröker <mbroeker@largo.homelinux.org>

diff --git a/Makefile b/Makefile
--- 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:
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 <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;
+}