From 6fb072f62c2f50118dd5cb377d10c76ece51e5fb Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sun, 4 Oct 2020 14:36:07 +0200 Subject: Setze srcut-Marker... --- quicksort.c | 380 +++++++++++++++++++++++++++++++----------------------------- 1 file changed, 199 insertions(+), 181 deletions(-) (limited to 'quicksort.c') diff --git a/quicksort.c b/quicksort.c index fa219e9..4657dcd 100644 --- a/quicksort.c +++ b/quicksort.c @@ -1,10 +1,12 @@ +#include #include #include -#include #include + #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 - - for ( ; ; ) - { - if ( root ) { // Teil 1: Konstruktion des Heaps - parent= --root; - val= data[root]; // zu versickernder Wert + 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 } - 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>1; - while (j>=start) - { if (v[j]>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); - -/* 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 */ - - + 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); + + /* 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; - - 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); - 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 - -- cgit v1.3