# HG changeset patch
# User Markus Bröker <mbroeker@largo.dyndns.tv>
# Date 1239879039 -7200
# Node ID 4103c76d5bf2d82beaef770f7ec21a29523e3e6e
# Parent  9ac5a589211e174834208b1c05e95f237304bbf7
sort.c: bubblesort fixed

 * the bubblesort algorithm has an abort-condition
 * the linearsort algorithm has not an abort-condition

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

diff --git a/sort.c b/sort.c
--- a/sort.c
+++ b/sort.c
@@ -40,7 +40,7 @@
 }
 
 /**
- * Laufzeitverhalten: n^2-1 Durchläufe zum Sortieren von n Elementen...
+ * Laufzeitverhalten: n^2-n Durchläufe zum Sortieren von n Elementen...
  */
 void lazysort (int *v, int n, int (*compare_func) (int *, int *))
 {
@@ -57,9 +57,9 @@
 }
 
 /**
- * Laufzeitverhalten: (1/2)*n^2-1 Durchläufe zum Sortieren von n Elementen...
+ * Laufzeitverhalten: (1/2)*n^2-n Durchläufe zum Sortieren von n Elementen...
  */
-void bubblesort (int *v, int n, int (*compare) (int *, int *))
+void linearsort (int *v, int n, int (*compare) (int *, int *))
 {
     int i, j;
 
@@ -70,6 +70,28 @@
             }
         }
     }
+    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");
 }
 
@@ -78,6 +100,7 @@
     int a[MAX];
     int b[MAX];
     int c[MAX];
+    int d[MAX];
 
     int i;
 
@@ -89,19 +112,21 @@
 
     memcpy (b, a, sizeof (a));
     memcpy (c, a, sizeof (a));
+    memcpy (d, a, sizeof (a));
 
     lazysort (a, MAX, &compare);
-    bubblesort (b, MAX, &compare);
+    linearsort (b, MAX, &compare);
+    bubblesort (c, MAX, &compare);
 
-    qsort (c, MAX, sizeof (int), (void *)&compare);
+    qsort (d, MAX, sizeof (int), (void *)&compare);
     statistic ("Quick");
 
     printf ("PRESS <RETURN> to CONTINUE");
     while (getchar () != 10);
-    printf ("%2c %2c %2c\n--------\n", 'L', 'B', 'Q');
+    printf ("%2c %2c %2c %2c\n-----------\n", 'L', 'N', 'B', 'Q');
 
     for (i = 0; i < MAX; i++)
-        printf ("%2d %2d %2d\n", a[i], b[i], c[i]);
+        printf ("%2d %2d %2d %2d\n", a[i], b[i], c[i], d[i]);
 
     return EXIT_SUCCESS;
 }