sort.c
changeset 72 4103c76d5bf2
parent 70 ded389a5dc2a
child 73 d0578510aea1
--- 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;
 }