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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
/*
** hugesort.c -- huge qsort() -- public domain by Raymond Gardner 6/92
** tested with Borland C++ 3.0 (C mode)
*/
static void swap(char huge *a, char huge *b, unsigned n)
{
char tmp;
do
{
tmp = *a; *a++ = *b; *b++ = tmp;
} while ( --n );
}
void hugesort(void huge *basep,
unsigned nel,
unsigned width,
int (*comp)(void huge *, void huge *))
{
char huge *i, huge *j;
unsigned int lnel, rnel;
char huge *base = (char huge *)basep;
while (nel > 1)
{
swap(base, base + (long)width * (nel / 2), width);
for (i = base, j = base + (long)width * nel; ; )
{
do
j -= width;
while ( (*comp)(j, base) > 0 );
do
i += width;
while ( i < j && (*comp)(i, base) < 0 );
if (i >= j)
break;
swap(i, j, width);
}
swap(j, base, width);
lnel = (unsigned)((long)(j - base) / width);
rnel = nel - lnel - 1;
j += width;
if (lnel < rnel)
{
hugesort(base, lnel, width, comp);
base = j;
nel = rnel;
}
else
{
hugesort(j, rnel, width, comp);
nel = lnel;
}
}
}
#ifdef TEST
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <alloc.h>
#define PADSIZE 300
typedef struct x {
int key;
char pad[PADSIZE];
} X;
int cmpv(void huge *a, void huge *b) /* (note void huge *) passed here */
{
return ((X huge *)a)->key < ((X huge *)b)->key ? -1 :
((X huge *)a)->key > ((X huge *)b)->key ? 1 : 0;
}
int main(int argc, char **argv)
{
X huge *v;
int n;
int i, j;
n = 300; /* default element count */
if (argc > 1)
n = atoi(argv[1]);
printf("test with %d elements\n", n);
v = farmalloc(sizeof(X) * (long)n);
assert(v); /* be sure we got memory */
for (i = 0; i < n; ++i) /* random init */
{
v[i].key = rand();
for (j = 0; j < PADSIZE; ++j)
v[i].pad[j] = rand();
}
for (i = 0; i < n; ++i) /* display before */
printf(" %d", v[i].key);
printf("\n");
hugesort(v, n, sizeof(X), cmpv); /* sort it */
for ( i = 0; i < n; ++i ) /* display after */
printf(" %d", v[i].key);
printf("\n");
return 0;
}
#endif
|
