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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
/*========== SNIP SNIP SNIP ==========*/
/* SORT.H */
void *sortl(void *list, void *(*getnext)(void *),
void (*setnext)(void *, void *),
int (*compare)(void *, void *));
/*========== SNIP SNIP SNIP ==========*/
/* SORT.C */
#include <stdlib.h>
#include "sort.h"
/*
This is a quicksort routine to be used to sort linked-lists
by Jon Guthrie.
*/
void *sortl(list, getnext, setnext, compare)
void *list, *(*getnext)(void *), (*setnext)(void *, void *);
int (*compare)(void *, void *);
{
void *low_list, *high_list, *current, *pivot, *temp;
int result;
/*
Test for empty list.
*/
if(NULL == list)
return(NULL);
/*
Find the first element that doesn't have the same value as the first
element.
*/
current = list;
do
{
current = getnext(current);
if(NULL == current)
return(list);
} while(0 == (result = compare(list, current)));
/*
My pivot value is the lower of the two. This insures that the sort
will always terminate by guaranteeing that there will be at least one
member of both of the sublists.
*/
if(result > 0)
pivot = current;
else
pivot = list;
/* Initialize the sublist pointers */
low_list = high_list = NULL;
/*
Now, separate the items into the two sublists
*/
current = list;
while(NULL != current)
{
temp = getnext(current);
if(compare(pivot, current) < 0)
{
/* add one to the high list */
setnext(current, high_list);
high_list = current;
}
else
{
/* add one to the low list */
setnext(current, low_list);
low_list = current;
}
current = temp;
}
/*
And, recursively call the sort for each of the two sublists.
*/
low_list = sortl(low_list, getnext, setnext, compare);
high_list = sortl(high_list, getnext, setnext, compare);
/*
Now, I have to put the "high" list after the end of the "low" list.
To do that, I first have to find the end of the "low" list...
*/
current = temp = low_list;
while(1)
{
current = getnext(current);
if(NULL == current)
break;
temp = current;
}
/*
Then, I put the "high" list at the end of the low list
*/
setnext(temp, high_list);
return(low_list);
}
/* mergesort linked lists by Ray Gardner */
/* split list into 2 parts, sort each recursively, merge */
void *sortl(p, getnext, setnext, compare)
void *p, *(*getnext)(void *), (*setnext)(void *, void *);
int (*compare)(void *, void *);
{
void *q, *r, *head;
if ( p ) { /* first split it */
r = p;
for ( q = getnext(r); q && (q = getnext(q)) != NULL; q = getnext(q) )
r = getnext(r);
q = getnext(r);
setnext(r, NULL);
if ( q ) { /* now sort each sublist */
p = sortl(p, getnext, setnext, compare);
q = sortl(q, getnext, setnext, compare);
if ( compare(q, p) < 0 ) { /* smallest item becomes list head */
head = q;
q = getnext(q);
} else {
head = p;
p = getnext(p);
}
for ( r = head; p && q; ) { /* now merge the lists under head */
if ( keycmp(q, p) < 0 ) {
setnext(r, q);
r = q;
q = getnext(q);
} else {
setnext(r, p);
r = p;
p = getnext(p);
}
}
setnext(r, (p ? p : q)); /* append the leftovers */
p = head;
}
}
return p;
}
|
