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
|
.\" placed in the public domain by Will Naylor -*- nroff -*-
.\" 1998-08-21 formatting added by Jim Van Zandt <jrv@vanzandt.mv.com>
.TH WNSORT 3 "August 23, 1998" "WNLIB" ""
.SH NAME
wn_sort_sll, wn_sort_ptrarray \- sorting package
.SH SYNOPSIS
.nf
.B #include <wn/wnsort.h>
.sp
.B wn_sort_sll(&\fIlist\fP,\fIpcompare_func\fP)
.B wn_sll \fIlist\fP;
.B int (*\fIpcompare_func\fP)(/*p1,p2*/); /* ptr p1,p2; */
.sp
.B wn_sort_ptrarray(\fIarray\fP,\fIsize\fP,\fIpcompare_func\fP)
.B ptr \fIarray\fP[];
.B int \fIsize\fP;
.B int (*\fIpcompare_func\fP)(/*p1,p2*/); /* ptr p1,p2; */
.SH DESCRIPTION
\fBwn_sort_sll\fP sorts a singly linked list into ascending order,
using a "merge sort" algorithm. (*\fIpcompare_func\fP)()
compares contents fields of 2 wn_sll's and returns
an int < == or > to 0, according to whether object
\fIp1\fP is < == or > to \fIp2\fP.
\fBwn_sort_ptrarray\fP sorts (in place) \fIarray\fP into ascending order,
using a "quick sort" algorithm.
\fIsize\fP is the number of entries in \fIarray\fP. (*\fIpcompare_func\fP)()
compares 2 \fIarray\fP entries and returns an int < == or > to 0, according
to whether object \fIp1\fP is < == or > to \fIp2\fP. Note that
\fBwn_sort_ptrarray\fP understands only pointers to structs, unlike qsort(3),
which can manipulate an \fIarray\fP of structs directly.
I recommend use of \fBwn_sort_sll\fP rather than \fBwn_sort_ptrarray\fP
because lists are generally simpler and more flexible than arrays.
See "wnrsrt" for a radix \fIlist\fP sort; this is often much faster
than \fBwn_sort_sll\fP or \fBwn_sort_ptrarray\fP.
If you must use an \fIarray\fP-based sort, I recommend use of
\fBwn_sort_ptrarray\fP rather than "qsort(3)" for the following reasons:
1) \fBwn_sort_ptrarray\fP 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) \fBwn_sort_ptrarray\fP is faster for non-degenerate data for several
reasons.
3) \fBwn_sort_ptrarray\fP is easier to understand.
.SH EXAMPLES
Both of the following subroutines
.nf
example1() /* list sort */
{
wn_sll \fIlist\fP,el;
char *string;
\fIlist\fP = NULL;
wn_sllins(&\fIlist\fP,"foo");
wn_sllins(&\fIlist\fP,"bar");
wn_sllins(&\fIlist\fP,"tim");
wn_sllins(&\fIlist\fP,"mouse");
wn_sllins(&\fIlist\fP,"ant");
wn_sllins(&\fIlist\fP,"turkey");
\fBwn_sort_sll\fP(&\fIlist\fP,(strcmp));
for(el=\fIlist\fP;el!=NULL;el=el->next)
{
string = el->contents;
printf("%s\n",string);
}
}
example2() /* array sort */
{
char *\fIarray\fP[] = {"foo","bar","tim","mouse","ant","turkey"};
int i;
\fBwn_sort_ptrarray\fP((ptr *)array,6,(strcmp));
for(i=0;i<6;i++)
{
printf("%s\n",\fIarray\fP[i]);
}
}
.fi
print the sorted strings
.nf
ant
bar
foo
mouse
tim
turkey
.fi
.SH RESOURCES
Both of these routines run with
WORST and AVERAGE CASE:
time = n*log(n)*<time for compare>
.br
stack memory = log(n)
.br
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 \fBwn_sort_sll\fP or \fBwn_sort_ptrarray\fP.
.\".SH DIAGNOSTICS
.\".SH BUGS
.SH "SEE ALSO"
wnsrtl, wnrsrt, qsort(3), wnsll, wnrndl, wnrndp
.SH AUTHOR
Will Naylor
|
