From 154874afda4a8df885e51c01f7681f04fb0b8e61 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 9 Apr 2022 09:43:53 +0200 Subject: neue Verzeichnisstruktur --- quicksort.c | 684 ------------------------------------------------------------ 1 file changed, 684 deletions(-) delete mode 100644 quicksort.c (limited to 'quicksort.c') diff --git a/quicksort.c b/quicksort.c deleted file mode 100644 index 4657dcd..0000000 --- a/quicksort.c +++ /dev/null @@ -1,684 +0,0 @@ -#include -#include -#include -#include - -#include "util.h" - -static int -bigrand(void) -{ - int x = (rand() << 24) | (rand() << 16) | (rand() << 8) | rand(); - if ( x < 0 ) - return -x; - return x; -} - -static int -randint(int l, int u) -{ - return l + bigrand() % (u - l + 1); -} - -typedef int T; - -static const int CUTOFF = 128; - -static inline void -swap(T a[], int i, int j) -{ - T t = a[i]; - a[i] = a[j]; - a[j] = t; -} - -static void -insertsort(T a[], int n) -{ - int i, j; - 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]; - a[j] = t; - } -} - -static void -quicksort(T a[], int n) -{ - int i, last; - - if ( n <= CUTOFF ) - return; - - swap(a, 0, bigrand() % n); - - last = 0; - for ( i = 1; i < n; ++i ) - if ( a[i] < a[0] ) - swap(a, ++last, i); - - swap(a, 0, last); - - quicksort(a, last); - quicksort(a + last + 1, n - last - 1); -} - -void -my_quicksort(T a[], int n) -{ - quicksort(a, 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; - return 0; -} - -void -c_quicksort(T a[], int n) -{ - assert(n >= 0); - qsort(a, (size_t) n, sizeof(T), cmp); -} - -/* This function takes last element as pivot, places - the pivot element at its correct position in sorted - 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 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); -} - -/* 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) -{ - while ( low < high ) { - /* pi is partitioning index, arr[p] is now - at right place */ - int pi = partition(arr, low, high); - - if ( pi - low < high - pi ) { - quickSort(arr, low, pi - 1); - low = pi + 1; - } - else { - quickSort(arr, pi + 1, high); - high = pi - 1; - } - } -} - -void -g4g_quicksort(T a[], int n) -{ - quickSort(a, 0, n - 1); -} - -static void -three_way_quicksort(int a[], int l, int r) -{ - int k; - T v = a[r]; - - if ( r <= l ) - return; - - int i = l - 1, j = r, p = l - 1, q = r; - - for ( ;; ) { - while ( a[++i] < v ) - ; - while ( v < a[--j] ) - if ( j == l ) - break; - if ( i >= j ) - break; - - swap(a, i, j); - - if ( a[i] == v ) - swap(a, ++p, i); - if ( v == a[j] ) - swap(a, --q, j); - } - swap(a, i, r); - j = i - 1; - i = i + 1; - - for ( k = l; k <= p; ++k, --j ) - swap(a, k, j); - 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) -{ - 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) - -static void -fixdown(T heap[], int i, int n) -{ - for ( ;; ) { - const int l = LEFT(i); - const int r = RIGHT(i); - int m = i; - - if ( l < n && heap[m] < heap[l] ) - m = l; - - if ( r < n && heap[m] < heap[r] ) - m = r; - - if ( m == i ) - break; - - swap(heap, m, i); - - i = m; - } -} - -static void -heapify(T heap[], int n) -{ - for ( int i = n / 2 - 1; i >= 0; --i ) - fixdown(heap, i, n); -} - -void -my_heapsort(T a[], int n) -{ - heapify(a, n); - - 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 -{ - 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 - } - 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 - --child; - - 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 - continue; - } - - 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 - } - - child = (parent - 1) >> 1; // 2 Ebenen nach oben zurück - } - - while ( child != root ) // maximal zum Ausgangspunkt zurück - { - 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 - - data[child] = data[parent]; // Rückverschiebung nötig - child = parent; // 1 Ebene nach oben zurück - } - - data[child] = val; // versickerten Wert eintragen - } -} - -/*----------------------------------------------------------------------*/ -/* BOTTOM-UP HEAPSORT */ -/* Written by J. Teuhola ; the original idea is */ -/* probably due to R.W. Floyd. Thereafter it has been used by many */ -/* authors, among others S. Carlsson and I. Wegener. Building the heap */ -/* bottom-up is also due to R. W. Floyd: Treesort 3 (Algorithm 245), */ -/* Communications of the ACM 7, p. 701, 1964. */ -/*----------------------------------------------------------------------*/ - -#define element float - -/*-----------------------------------------------------------------------*/ -/* The sift-up procedure sinks a hole from v[i] to leaf and then sifts */ -/* 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) -{ - int j, start; - T x; - - start = i; - 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; - } - j = i >> 1; - while ( j >= start ) { - if ( v[j] < x ) { - v[i] = v[j]; - i = j; - j = i >> 1; - } - else - break; - } - v[i] = x; -} /* 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) -{ - 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) -{ - int i, last; - - if ( n <= CUTOFF ) - return; - - if ( --h == 1 ) { - my_heapsort(a, n); - return; - } - - swap(a, 0, bigrand() % n); - - last = 0; - for ( i = 1; i < n; ++i ) - if ( a[i] < a[0] ) - swap(a, ++last, i); - - swap(a, 0, last); - - introsort(a, last, h); - introsort(a + last + 1, n - last - 1, h); -} - -void -my_introsort(T a[], int n) -{ - int h = 1; - - for ( int nn = 1; nn < n; nn <<= 1 ) - ++h; - - introsort(a, n, h); - insertsort(a, n); -} - -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]; - int i = l; - 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); -} - -void -pp_quicksort(T a[], int n) -{ - pp_quicksort_impl(a, 0, n - 1); - insertsort(a, n); -} - -static void -pp_quicksort_impl_it(T a[], int l, int u, int h) -{ - if ( --h == 1 ) { - my_heapsort(a + l, u - l + 1); - return; - } - - while ( u - l >= CUTOFF ) { - swap(a, l, randint(l, u)); - - 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 ); - 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); - l = j + 1; - } - else { - pp_quicksort_impl_it(a, j + 1, u, h); - u = j - 1; - } - } -} - -void -pp_quicksort_it(T a[], int n) -{ - int h = 1; - - for ( int nn = 1; nn < n; nn <<= 1 ) - ++h; - - pp_quicksort_impl_it(a, 0, n - 1, h); - insertsort(a, n); -} - -int -binary_search(T x, T v[], int n) -{ - int low, high; - - low = 0; - high = n - 1; - while ( low <= high ) { - int mid = low + ((high - low) / 2); - if ( x > v[mid] ) - low = mid + 1; - else if ( x < v[mid] ) - high = mid - 1; - else - return mid; - } - return -1; -} - -int -lower_bound(T x, T v[], int n) -{ - int low, high; - - low = 0; - high = n; - while ( low < high ) { - int mid = low + ((high - low) / 2); - - if ( x > v[mid] ) - low = mid + 1; - else - high = mid; - } - return x == v[low] ? low : -1; -} - -int -upper_bound(T x, T v[], int n) -{ - int low, high; - - low = 0; - high = n; - while ( low < high ) { - int mid = low + ((high - low) / 2); - - if ( x >= v[mid] ) - low = mid + 1; - else - high = mid; - } - return (low > 0 && x == v[low - 1]) ? low - 1 : -1; -} - -/* TESTTREIBER */ - -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) -{ - for ( int i = 0; i < n; ++i ) - a[i] = bigrand() % 100; -} - -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) -{ - for ( int i = n; i >= 0; --i ) - a[i] = i; -} - -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) -{ - for ( int i = 1; i < n; ++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)) -{ - T * a; - clock_t start, ende; - - a = malloc(sizeof(T) * (size_t) n); - - (*gen_testset)(a, n); - - start = clock(); - (*do_sort)(a, n); - ende = clock(); - - test_sorting(a, n); - - free(a); - - printf("%10.3lf sec", ((double) ende - start) / CLOCKS_PER_SEC); - fflush(stdout); -} - -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); - do_one_test(n, do_sort, gen_testset_random2); - do_one_test(n, do_sort, gen_testset_asc); - do_one_test(n, do_sort, gen_testset_desc); - do_one_test(n, do_sort, gen_testset_unique); - putchar('\n'); -} - -/* ENDE TESTTREIBER */ - -int -main(void) -{ - const int n = 20000000; - - srand(time(0)); - do_all_tests("my_heapsort", n, my_heapsort); - do_all_tests("heapsort_bu", n, heapsort_bu); - do_all_tests("bottom_up_heapsort", n, bottom_up_heapsort); - do_all_tests("c_quicksort", n, c_quicksort); - //do_all_tests("g4g_quicksort", n, g4g_quicksort); - //do_all_tests("sed_quicksort", n, sed_quicksort); - do_all_tests("my_introsort", n, my_introsort); - //do_all_tests("my_quicksort", n, my_quicksort); - do_all_tests("pp_quicksort", n, pp_quicksort); - do_all_tests("pp_quicksort_it", n, pp_quicksort_it); - - return 0; -} - -#if 0 -int _main(void) -{ - T array[20]; - - for ( int i = 0; i != NELEM(array); ++i ) - array[i] = rand() % 10; - - sort(array, NELEM(array)); - print(array, NELEM(array)); - - int value; - while ( scanf("%d", &value) == 1 && value != -1 ) { - int bs = binary_search(value, array, NELEM(array)); - int lb = lower_bound(value, array, NELEM(array)); - int ub = upper_bound(value, array, NELEM(array)); - - printf("bs: %d - lb: %d - ub: %d\n", bs, lb, ub); - } - - return EXIT_SUCCESS; -} -#endif -- cgit v1.3