From 154874afda4a8df885e51c01f7681f04fb0b8e61 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 9 Apr 2022 09:43:53 +0200 Subject: neue Verzeichnisstruktur --- shellsort.c | 63 ------------------------------------------------------------- 1 file changed, 63 deletions(-) delete mode 100644 shellsort.c (limited to 'shellsort.c') diff --git a/shellsort.c b/shellsort.c deleted file mode 100644 index 29e6bf8..0000000 --- a/shellsort.c +++ /dev/null @@ -1,63 +0,0 @@ -#include -#include -#include - -#include "util.h" - -typedef int T; - -void -shellsort(T a[], size_t n) -{ - //static const size_t gaps[] = { 701, 301, 132, 57, 23, 10, 4, 1 }; - - // Wikipedia: - //static const size_t gaps[] = { 2147483647, 1131376761, 410151271, 157840433, 58548857, 21521774, 8810089, 3501671, 1355339, 543749, 213331, 84801, 27901, 11969, 4711, 1968, 815, 271, 111, 41, 13, 4, 1 }; - - // https://www.cs.princeton.edu/~rs/shell/paperF.pdf - static const size_t gaps[] = { 1391376, 463792, 198768, 86961, 33936, 13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1 }; - - for ( size_t k = 0; k < NELEM(gaps); ++k ) { - const size_t gap = gaps[k]; - - for ( size_t i = gap; i < n; i++ ) { - size_t j = i; - T temp = a[i]; - - for ( ; j >= gap && a[j - gap] > temp; j -= gap ) - a[j] = a[j - gap]; - - a[j] = temp; - } - } -} - -static void -test(T a[], size_t n) -{ - for ( size_t i = 1; i < n; ++i ) { - if ( a[i - 1] > a[i] ) { - ERROR("sortierung passt nicht"); - } - } -} - -int -main(void) -{ - T a[1000000]; - - srand(time(NULL)); - for ( size_t i = 0; i != NELEM(a); ++i ) - a[i] = rand() % 1000; - - clock_t start = clock(); - shellsort(a, NELEM(a)); - clock_t end = clock(); - - test(a, NELEM(a)); - - printf("duration: %.3f sec\n", ((double) (end - start)) / CLOCKS_PER_SEC); - - return EXIT_SUCCESS; -} -- cgit v1.3