Setze srcut-Marker...

1 files changed, 194 insertions, 176 deletions

diff --git a/quicksort.c b/quicksort.c
index fa219e9..4657dcd 100644
--- a/quicksort.c
+++ b/quicksort.c
@@ -1,10 +1,12 @@
+#include <assert.h>
 #include <stdio.h>
 #include <stdlib.h>
-#include <assert.h>
 #include <time.h>
+
 #include "util.h"
 
-static int bigrand(void)
+static int
+bigrand(void)
 {
         int x = (rand() << 24) | (rand() << 16) | (rand() << 8) | rand();
         if ( x < 0 )
@@ -12,9 +14,10 @@ static int bigrand(void)
         return x;
 }
 
-static int randint(int l, int u)
+static int
+randint(int l, int u)
 {
-        return l + bigrand() % (u-l+1);
+        return l + bigrand() % (u - l + 1);
 }
 
 typedef int T;
@@ -24,7 +27,7 @@ static const int CUTOFF = 128;
 static inline void
 swap(T a[], int i, int j)
 {
-        T t = a[i];
+        T t  = a[i];
         a[i] = a[j];
         a[j] = t;
 }
@@ -33,11 +36,10 @@ static void
 insertsort(T a[], int n)
 {
         int i, j;
-        for ( i = 1; i < n; ++i )
-        {
+        for ( i = 1; i < n; ++i ) {
                 T t = a[i];
-                for ( j = i; j > 0 && a[j-1] > t; --j )
-                        a[j] = a[j-1];
+                for ( j = i; j > 0 && a[j - 1] > t; --j )
+                        a[j] = a[j - 1];
                 a[j] = t;
         }
 }
@@ -60,7 +62,7 @@ quicksort(T a[], int n)
         swap(a, 0, last);
 
         quicksort(a, last);
-        quicksort(a+last+1, n-last-1);
+        quicksort(a + last + 1, n - last - 1);
 }
 
 void
@@ -70,22 +72,24 @@ my_quicksort(T a[], int n)
         insertsort(a, n);
 }
 
-
 static int
 cmp(const void *a, const void *b)
 {
         const int *pa = (const T *) a;
         const int *pb = (const T *) b;
 
-        if ( *pa < *pb ) return -1;
-        if ( *pa > *pb ) return  1;
+        if ( *pa < *pb )
+                return -1;
+        if ( *pa > *pb )
+                return 1;
         return 0;
 }
 
 void
 c_quicksort(T a[], int n)
 {
-        qsort(a, n, sizeof(T), cmp);
+        assert(n >= 0);
+        qsort(a, (size_t) n, sizeof(T), cmp);
 }
 
 /* This function takes last element as pivot, places
@@ -93,65 +97,63 @@ c_quicksort(T a[], int n)
     array, and places all smaller (smaller than pivot)
    to left of pivot and all greater elements to right
    of pivot */
-int partition (int arr[], int low, int high)
+int
+partition(int arr[], int low, int high)
 {
-    int pivot = arr[high];    // pivot
-    int i = (low - 1);  // Index of smaller element
+        int pivot = arr[high]; // pivot
+        int i     = (low - 1); // Index of smaller element
 
-    for (int j = low; j <= high- 1; j++)
-    {
-        // If current element is smaller than or
-        // equal to pivot
-        if (arr[j] <= pivot)
-        {
-            i++;    // increment index of smaller element
-            swap(arr, i, j);
-        }
-    }
-    swap(arr, i + 1, high);
-    return (i + 1);
+        for ( int j = low; j <= high - 1; j++ ) {
+                // If current element is smaller than or
+                // equal to pivot
+                if ( arr[j] <= pivot ) {
+                        i++; // increment index of smaller element
+                        swap(arr, i, j);
+                }
+        }
+        swap(arr, i + 1, high);
+        return (i + 1);
 }
 
 /* The main function that implements QuickSort
  arr[] --> Array to be sorted,
   low  --> Starting index,
   high  --> Ending index */
-void quickSort(int arr[], int low, int high)
+void
+quickSort(int arr[], int low, int high)
 {
-    while (low < high)
-    {
-        /* pi is partitioning index, arr[p] is now
+        while ( low < high ) {
+                /* pi is partitioning index, arr[p] is now
            at right place */
-        int pi = partition(arr, low, high);
+                int pi = partition(arr, low, high);
 
-        if (pi - low < high - pi)
-        {
+                if ( pi - low < high - pi ) {
                         quickSort(arr, low, pi - 1);
                         low = pi + 1;
                 }
-                else
-                {
+                else {
                         quickSort(arr, pi + 1, high);
                         high = pi - 1;
                 }
-    }
+        }
 }
 
-void g4g_quicksort(T a[], int n)
+void
+g4g_quicksort(T a[], int n)
 {
-        quickSort(a, 0, n-1);
+        quickSort(a, 0, n - 1);
 }
 
-
-static void three_way_quicksort(int a[], int l, int r)
+static void
+three_way_quicksort(int a[], int l, int r)
 {
         int k;
-        T v = a[r];
+        T   v = a[r];
 
         if ( r <= l )
                 return;
 
-        int i = l-1, j = r, p = l-1, q = r;
+        int i = l - 1, j = r, p = l - 1, q = r;
 
         for ( ;; ) {
                 while ( a[++i] < v )
@@ -169,27 +171,30 @@ static void three_way_quicksort(int a[], int l, int r)
                 if ( v == a[j] )
                         swap(a, --q, j);
         }
-        swap(a, i, r); j = i-1; i = i+1;
+        swap(a, i, r);
+        j = i - 1;
+        i = i + 1;
 
-        for ( k = l  ; k <= p; ++k, --j )
+        for ( k = l; k <= p; ++k, --j )
                 swap(a, k, j);
-        for ( k = r-1; k >= q; --k, ++i )
+        for ( k = r - 1; k >= q; --k, ++i )
                 swap(a, k, i);
 
         three_way_quicksort(a, l, j);
         three_way_quicksort(a, i, r);
 }
 
-void sed_quicksort(int a[], int n)
+void
+sed_quicksort(int a[], int n)
 {
-        three_way_quicksort(a, 0, n-1);
+        three_way_quicksort(a, 0, n - 1);
 }
 
 /* ====================== HEAPSORT ======================= */
 
-#define LEFT(idx)       (idx*2+1)
-#define RIGHT(idx)      (idx*2+2)
-#define PARENT(idx)     ((idx-1)/2)
+#define LEFT(idx) (idx * 2 + 1)
+#define RIGHT(idx) (idx * 2 + 2)
+#define PARENT(idx) ((idx - 1) / 2)
 
 static void
 fixdown(T heap[], int i, int n)
@@ -197,7 +202,7 @@ fixdown(T heap[], int i, int n)
         for ( ;; ) {
                 const int l = LEFT(i);
                 const int r = RIGHT(i);
-                int m = i;
+                int       m = i;
 
                 if ( l < n && heap[m] < heap[l] )
                         m = l;
@@ -226,76 +231,73 @@ my_heapsort(T a[], int n)
 {
         heapify(a, n);
 
-        for ( int i = n-1; i >= 0; --i ) {
+        for ( int i = n - 1; i >= 0; --i ) {
                 swap(a, 0, i);
                 fixdown(a, 0, i);
         }
 }
 
 void
-heapsort_bu( T * data, int n ) // zu sortierendes Feld und seine Länge
+heapsort_bu(T *data, int n) // zu sortierendes Feld und seine Länge
 {
-        T val;
+        T   val;
         int parent, child;
-        int root= n >> 1;                  // erstes Blatt im Baum
-        int count= 0;                      // Zähler für Anzahl der Vergleiche
+        int root  = n >> 1; // erstes Blatt im Baum
+        int count = 0;      // Zähler für Anzahl der Vergleiche
 
-        for ( ; ; )
-        {
-                if ( root ) {                    // Teil 1: Konstruktion des Heaps
-                        parent= --root;
-                        val= data[root];               // zu versickernder Wert
+        for ( ;; ) {
+                if ( root ) { // Teil 1: Konstruktion des Heaps
+                        parent = --root;
+                        val    = data[root]; // zu versickernder Wert
                 }
-                else
-                        if ( --n ) {                     // Teil 2: eigentliche Sortierung
-                                val= data[n];                  // zu versickernder Wert vom Heap-Ende
-                                data[n]= data[0];              // Spitze des Heaps hinter den Heap in
-                                parent= 0;                     //   den sortierten Bereich verschieben
-                        }
-                        else                             // Heap ist leer; Sortierung beendet
-                                break;
+                else if ( --n ) {      // Teil 2: eigentliche Sortierung
+                        val     = data[n]; // zu versickernder Wert vom Heap-Ende
+                        data[n] = data[0]; // Spitze des Heaps hinter den Heap in
+                        parent  = 0;       //   den sortierten Bereich verschieben
+                }
+                else // Heap ist leer; Sortierung beendet
+                        break;
 
-                while ( (child= (parent + 1) << 1) < n )  // zweites (!) Kind;
-                {                                         // Abbruch am Ende des Heaps
-                        if ( ++count, data[child-1] > data[child] )  // größeres Kind wählen
+                while ( (child = (parent + 1) << 1) < n )         // zweites (!) Kind;
+                {                                                 // Abbruch am Ende des Heaps
+                        if ( ++count, data[child - 1] > data[child] ) // größeres Kind wählen
                                 --child;
 
-                        data[parent]= data[child];     // größeres Kind nach oben rücken
-                        parent= child;                 // in der Ebene darunter weitersuchen
+                        data[parent] = data[child]; // größeres Kind nach oben rücken
+                        parent       = child;       // in der Ebene darunter weitersuchen
                 }
 
-                if ( child == n )                // ein einzelnes Kind am Heap-Ende
-                {                                //   ist übersprungen worden
-                        if ( ++count, data[--child] >= val ) {  // größer als der zu versick-
-                                data[parent]= data[child];   //   ernde Wert, also noch nach oben
-                                data[child]= val;            // versickerten Wert eintragen
+                if ( child == n )                          // ein einzelnes Kind am Heap-Ende
+                {                                          //   ist übersprungen worden
+                        if ( ++count, data[--child] >= val ) { // größer als der zu versick-
+                                data[parent] = data[child];        //   ernde Wert, also noch nach oben
+                                data[child]  = val;                // versickerten Wert eintragen
                                 continue;
                         }
 
-                        child= parent;                 // 1 Ebene nach oben zurück
+                        child = parent; // 1 Ebene nach oben zurück
                 }
-                else
-                {
-                        if ( ++count, data[parent] >= val ) {  // das Blatt ist größer als der
-                                data[parent]= val;           //   zu versickernde Wert, der damit
-                                continue;                    //   direkt eingetragen werden kann
+                else {
+                        if ( ++count, data[parent] >= val ) { // das Blatt ist größer als der
+                                data[parent] = val;               //   zu versickernde Wert, der damit
+                                continue;                         //   direkt eingetragen werden kann
                         }
 
-                        child= (parent - 1) >> 1;      // 2 Ebenen nach oben zurück
+                        child = (parent - 1) >> 1; // 2 Ebenen nach oben zurück
                 }
 
-                while ( child != root )          // maximal zum Ausgangspunkt zurück
+                while ( child != root ) // maximal zum Ausgangspunkt zurück
                 {
-                        parent= (child - 1) >> 1;      // den Vergleichswert haben wir bereits
+                        parent = (child - 1) >> 1; // den Vergleichswert haben wir bereits
                         //   nach oben verschoben
-                        if ( ++count, data[parent] >= val )  // größer als der zu versickernde
-                                break;                             //   Wert, also Position gefunden
+                        if ( ++count, data[parent] >= val ) // größer als der zu versickernde
+                                break;                          //   Wert, also Position gefunden
 
-                        data[child]= data[parent];     // Rückverschiebung nötig
-                        child= parent;                 // 1 Ebene nach oben zurück
+                        data[child] = data[parent]; // Rückverschiebung nötig
+                        child       = parent;       // 1 Ebene nach oben zurück
                 }
 
-                data[child]= val;                // versickerten Wert eintragen
+                data[child] = val; // versickerten Wert eintragen
         }
 }
 
@@ -315,65 +317,67 @@ heapsort_bu( T * data, int n ) // zu sortierendes Feld und seine Länge
 /* the original v[i] element from the leaf level up. This is the main    */
 /* idea of bottom-up heapsort.                                           */
 /*-----------------------------------------------------------------------*/
-static void siftup(T v[], int i, int n)
+static void
+siftup(T v[], int i, int n)
 {
         int j, start;
-        T x;
+        T   x;
 
         start = i;
-        x = v[i];
-        j = i<<1;
-        while (j<=n)
-        {
-                if (j<n)
-                        if (v[j]<v[j+1])
+        x     = v[i];
+        j     = i << 1;
+        while ( j <= n ) {
+                if ( j < n )
+                        if ( v[j] < v[j + 1] )
                                 j++;
                 v[i] = v[j];
-                i = j; j = i<<1;
+                i    = j;
+                j    = i << 1;
         }
-        j = i>>1;
-        while (j>=start)
-        { if (v[j]<x)
-                { v[i] = v[j];
-                        i = j; j = i>>1;
+        j = i >> 1;
+        while ( j >= start ) {
+                if ( v[j] < x ) {
+                        v[i] = v[j];
+                        i    = j;
+                        j    = i >> 1;
                 }
-                else break;
+                else
+                        break;
         }
         v[i] = x;
-}                                /* End of siftup */
+} /* End of siftup */
 
 /*----------------------------------------------------------------------*/
 /* The heapsort procedure; the original array is r[0..n-1], but here    */
 /* it is shifted to vector v[1..n], for convenience.                     */
 /*----------------------------------------------------------------------*/
-void bottom_up_heapsort(T r[], int n)
+void
+bottom_up_heapsort(T r[], int n)
 {
-  int k; 
-  T x;
-  T *v;
-
-  v = r-1;                   /* The address shift */
-
-/* Build the heap bottom-up, using siftup. */
-  for (k=n>>1; k>1; k--) siftup(v, k, n);
+        int k;
+        T   x;
+        T * v;
 
-/* The main loop of sorting follows. The root is swapped with the last  */
-/* leaf after each sift-up. */
-  for (k=n; k>1; k--)
-    {
-      siftup(v, 1, k);
-      x = v[k]; v[k] = v[1]; v[1] = x;
-    }
-}                                /* End of bottom_up_heapsort */
+        v = r - 1; /* The address shift */
 
+        /* Build the heap bottom-up, using siftup. */
+        for ( k = n >> 1; k > 1; k-- )
+                siftup(v, k, n);
 
+        /* The main loop of sorting follows. The root is swapped with the last  */
+        /* leaf after each sift-up. */
+        for ( k = n; k > 1; k-- ) {
+                siftup(v, 1, k);
+                x    = v[k];
+                v[k] = v[1];
+                v[1] = x;
+        }
+} /* End of bottom_up_heapsort */
 
 /* ====================== HEAPSORT ======================= */
 
 /* ====================== INTROSORT ======================= */
 
-
-
 static void
 introsort(T a[], int n, int h)
 {
@@ -397,7 +401,7 @@ introsort(T a[], int n, int h)
         swap(a, 0, last);
 
         introsort(a, last, h);
-        introsort(a+last+1, n-last-1, h);
+        introsort(a + last + 1, n - last - 1, h);
 }
 
 void
@@ -412,67 +416,74 @@ my_introsort(T a[], int n)
         insertsort(a, n);
 }
 
-static void pp_quicksort_impl(T a[], int l, int u)
+static void
+pp_quicksort_impl(T a[], int l, int u)
 {
         if ( u - l < CUTOFF )
                 return;
 
         swap(a, l, randint(l, u));
 
-        T t = a[l];
+        T   t = a[l];
         int i = l;
-        int j = u+1;
-        for (;;) {
-                do i++; while ( /*i <= u &&*/ a[i] < t );
-                do j--; while ( a[j] > t );
+        int j = u + 1;
+        for ( ;; ) {
+                do
+                        i++;
+                while ( /*i <= u &&*/ a[i] < t );
+                do
+                        j--;
+                while ( a[j] > t );
                 if ( i > j )
                         break;
                 swap(a, i, j);
         }
         swap(a, l, j);
-        pp_quicksort_impl(a, l, j-1);
-        pp_quicksort_impl(a, j+1, u);
+        pp_quicksort_impl(a, l, j - 1);
+        pp_quicksort_impl(a, j + 1, u);
 }
 
 void
 pp_quicksort(T a[], int n)
 {
-        pp_quicksort_impl(a, 0, n-1);
+        pp_quicksort_impl(a, 0, n - 1);
         insertsort(a, n);
 }
 
-static void pp_quicksort_impl_it(T a[], int l, int u, int h)
+static void
+pp_quicksort_impl_it(T a[], int l, int u, int h)
 {
         if ( --h == 1 ) {
-                my_heapsort(a+l, u-l+1);
+                my_heapsort(a + l, u - l + 1);
                 return;
         }
 
-        while ( u-l >= CUTOFF )
-        {
+        while ( u - l >= CUTOFF ) {
                 swap(a, l, randint(l, u));
 
-                T t = a[l];
+                T   t = a[l];
                 int i = l;
-                int j = u+1;
+                int j = u + 1;
 
-                for (;;) {
-                        do i++; while ( /*i <= u && */ a[i] < t );
-                        do j--; while ( a[j] > t );
+                for ( ;; ) {
+                        do
+                                i++;
+                        while ( /*i <= u && */ a[i] < t );
+                        do
+                                j--;
+                        while ( a[j] > t );
                         if ( i > j )
                                 break;
                         swap(a, i, j);
                 }
                 swap(a, l, j);
 
-                if ( j - l < u - j ) 
-                {
-                        pp_quicksort_impl_it(a, l, j-1, h);
+                if ( j - l < u - j ) {
+                        pp_quicksort_impl_it(a, l, j - 1, h);
                         l = j + 1;
                 }
-                else
-                {
-                        pp_quicksort_impl_it(a, j+1, u, h);
+                else {
+                        pp_quicksort_impl_it(a, j + 1, u, h);
                         u = j - 1;
                 }
         }
@@ -486,7 +497,7 @@ pp_quicksort_it(T a[], int n)
         for ( int nn = 1; nn < n; nn <<= 1 )
                 ++h;
 
-        pp_quicksort_impl_it(a, 0, n-1, h);
+        pp_quicksort_impl_it(a, 0, n - 1, h);
         insertsort(a, n);
 }
 
@@ -495,8 +506,8 @@ binary_search(T x, T v[], int n)
 {
         int low, high;
 
-        low = 0;
-        high = n-1;
+        low  = 0;
+        high = n - 1;
         while ( low <= high ) {
                 int mid = low + ((high - low) / 2);
                 if ( x > v[mid] )
@@ -514,7 +525,7 @@ lower_bound(T x, T v[], int n)
 {
         int low, high;
 
-        low = 0;
+        low  = 0;
         high = n;
         while ( low < high ) {
                 int mid = low + ((high - low) / 2);
@@ -532,7 +543,7 @@ upper_bound(T x, T v[], int n)
 {
         int low, high;
 
-        low = 0;
+        low  = 0;
         high = n;
         while ( low < high ) {
                 int mid = low + ((high - low) / 2);
@@ -542,57 +553,63 @@ upper_bound(T x, T v[], int n)
                 else
                         high = mid;
         }
-        return ( low > 0 && x == v[low-1] ) ? low-1 : -1;
+        return (low > 0 && x == v[low - 1]) ? low - 1 : -1;
 }
 
 /* TESTTREIBER */
 
-
-void gen_testset_random(T a[], int n)
+void
+gen_testset_random(T a[], int n)
 {
         for ( int i = 0; i < n; ++i )
                 a[i] = bigrand();
 }
 
-void gen_testset_random2(T a[], int n)
+void
+gen_testset_random2(T a[], int n)
 {
         for ( int i = 0; i < n; ++i )
                 a[i] = bigrand() % 100;
 }
 
-void gen_testset_asc(T a[], int n)
+void
+gen_testset_asc(T a[], int n)
 {
         for ( int i = 0; i < n; ++i )
                 a[i] = i;
 }
 
-void gen_testset_desc(T a[], int n)
+void
+gen_testset_desc(T a[], int n)
 {
         for ( int i = n; i >= 0; --i )
                 a[i] = i;
 }
 
-void gen_testset_unique(T a[], int n)
+void
+gen_testset_unique(T a[], int n)
 {
         for ( int i = 0; i < n; ++i )
                 a[i] = 1;
 }
 
-void test_sorting(T a[], int n)
+void
+test_sorting(T a[], int n)
 {
         for ( int i = 1; i < n; ++i )
-                if ( a[i-1] > a[i] ) {
+                if ( a[i - 1] > a[i] ) {
                         puts("Fehler!");
                         exit(EXIT_SUCCESS);
                 }
 }
 
-void do_one_test(int n, void (*do_sort)(T a[], int n), void (*gen_testset)(T a[], int n))
+void
+do_one_test(int n, void (*do_sort)(T a[], int n), void (*gen_testset)(T a[], int n))
 {
-        T *a;
+        T *     a;
         clock_t start, ende;
 
-        a = malloc(sizeof(T) * n);
+        a = malloc(sizeof(T) * (size_t) n);
 
         (*gen_testset)(a, n);
 
@@ -608,7 +625,8 @@ void do_one_test(int n, void (*do_sort)(T a[], int n), void (*gen_testset)(T a[]
         fflush(stdout);
 }
 
-void do_all_tests(const char *msg, int n, void (*do_sort)(T a[], int n))
+void
+do_all_tests(const char *msg, int n, void (*do_sort)(T a[], int n))
 {
         printf("%-15.15s n=%-10d: ", msg, n);
         do_one_test(n, do_sort, gen_testset_random);
@@ -621,7 +639,8 @@ void do_all_tests(const char *msg, int n, void (*do_sort)(T a[], int n))
 
 /* ENDE TESTTREIBER */
 
-int main(void)
+int
+main(void)
 {
         const int n = 20000000;
 
@@ -663,4 +682,3 @@ int _main(void)
         return EXIT_SUCCESS;
 }
 #endif
-