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
|
#include <stdio.h> /* for typedef of void only */
/***********************************************************************
TeXindex uses the standard Unix library function qsort() for
record sorting. Unfortunately, qsort() is not a stable sorting
algorithm, so input order is not necessarily preserved for equal
sort keys. This is important, because the sorting is
case-independent, while the actual entries may not be. For
example, the input
\entry{i}{22}{{\CODE{i}}}
\entry{i}{42}{{\CODE{i}}}
\entry{I}{41}{{\CODE{I}}}
\entry{I}{42}{{\CODE{I}}}
produces
\initial {I}
\entry {{\CODE{i}}}{22}
\entry {{\CODE{I}}}{41--42}
\entry {{\CODE{i}}}{42}
instead of the correct
\initial {I}
\entry {{\CODE{i}}}{22, 42}
\entry {{\CODE{I}}}{41--42}
We therefore provide this stable shellsort replacement for
qsort() based on the code given on p. 116 of Kernighan and
Ritchie, ``The C Programming Language'', Prentice-Hall (1978).
This has order N**1.5 average performance, which is usually
slower than qsort(). In the interests of simplicity, we make no
attempt to handle short sequences by alternative methods.
[07-Nov-86]
***********************************************************************/
#define BASE(i) &base[(i)*width]
void
qsort(base, nel, width, compar)
char base[]; /* start of data in memory */
int nel; /* number of elements to be sorted */
int width; /* size (in bytes) of each element */
int (*compar)(); /* comparison function */
{
int gap;
int i;
int j;
register int k; /* inner exchange loop parameters */
register char* p;
register char* q;
register char c;
for (gap = nel/2; gap > 0; gap /= 2)
{
for (i = gap; i < nel; i++)
{
for (j = i-gap; j >= 0; j -= gap)
{
p = BASE(j);
q = BASE(j+gap);
if ((*compar)(p,q) <= 0)
break; /* exit j loop */
else
{
for (k = 0; k < width; (++p, ++q, ++k))
{
c = *q;
*q = *p;
*p = c;
}
}
}
}
}
}
|