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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
NAME
wnsort -- sorting package
SYNOPSIS
#include "wnsort.h"
wn_sort_sll(&list,pcompare_func)
wn_sll list;
int (*pcompare_func)(/*p1,p2*/); /* ptr p1,p2; */
wn_sort_ptrarray(array,size,pcompare_func)
ptr array[];
int size;
int (*pcompare_func)(/*p1,p2*/); /* ptr p1,p2; */
DESCRIPTION
"wn_sort_sll" sorts a singly linked list into ascending order,
using a "merge sort" algorithm. (*pcompare_func)()
compares contents fields of 2 wn_sll's and returns
an int < == or > to 0, according to whether object
"p1" is < == or > to "p2".
"wn_sort_ptrarray" sorts (in place) "array" into ascending order,
using a "quick sort" algorithm.
"size" is the number of entries in "array". (*pcompare_func)()
compares 2 array entries and returns an int < == or > to 0, according
to whether object "p1" is < == or > to "p2". Note that
"wn_sort_ptrarray" understands only pointers to structs, unlike qsort(3),
which can manipulate an array of structs directly.
I recommend use of "wn_sort_sll" rather than "wn_sort_ptrarray"
because lists are generally simpler and more flexible than arrays.
See "wnrsrt" for a radix list sort; this is often much faster
than "wn_sort_sll" or "wn_sort_ptrarray".
If you must use an array-based sort, I recommend use of
"wn_sort_ptrarray" rather than "qsort(3)" for the following reasons:
1) "wn_sort_ptrarray" has no degenerate cases, unlike qsort(3). If
qsort(3) is passed sorted or almost sorted data or
data with many of the keys equal, it degenerates into a
time=n^2 algorithm.
2) "wn_sort_ptrarray" is faster for non-degenerate data for several
reasons.
3) "wn_sort_ptrarray" is easier to understand.
EXAMPLES
Both of the following subroutines
example1() /* list sort */
{
wn_sll list,el;
char *string;
list = NULL;
wn_sllins(&list,"foo");
wn_sllins(&list,"bar");
wn_sllins(&list,"tim");
wn_sllins(&list,"mouse");
wn_sllins(&list,"ant");
wn_sllins(&list,"turkey");
wn_sort_sll(&list,(strcmp));
for(el=list;el!=NULL;el=el->next)
{
string = el->contents;
printf("%s\n",string);
}
}
example2() /* array sort */
{
char *array[] = {"foo","bar","tim","mouse","ant","turkey"};
int i;
wn_sort_ptrarray((ptr *)array,6,(strcmp));
for(i=0;i<6;i++)
{
printf("%s\n",array[i]);
}
}
print the sorted strings
ant
bar
foo
mouse
tim
turkey
RESOURCES
Both of these routines run with
WORST and AVERAGE CASE:
time = n*log(n)*<time for compare>
stack memory = log(n)
dynamic memory = 0
where n is the number of items to sort.
See "wnrsrt" for a radix list sort; this is often much faster
than "wn_sort_sll" or "wn_sort_ptrarray".
DIAGNOSTICS
BUGS
SEE ALSO
wnsrtl, wnrsrt, qsort(3), wnsll, wnrndl, wnrndp
AUTHOR
Will Naylor
|
