1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#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;
}
|
