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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
|
template <class Type>
struct nodeTypeCount
{
Type info;
long counter;
nodeTypeCount<Type> *link;
};
template<class Type>
void linkedListType<Type>::divide(nodeType<Type>* pivot, nodeType<Type>* &greater, nodeType<Type>* &smaller){
/* divids the list into 3 sublists based on the pivot value:
1) 'pivot' will be the list of elements equal to the pivot value
2) 'greater' will be the list of elements greater than the pivot value
3) 'smaller' will be the list of elements smaller than the pivot value
*/
// make sure that greater and smaller are not valid pointers
greater = NULL;
smaller = NULL;
// check if the original list is empty
if (pivot == NULL)
return;
// if we're here, we know that list is non-empty
// check if the list has only one element
// if that's the case, then we've got nothing to do
if (pivot -> link == NULL)
return;
// if we're here, the list has at least two elements,
// so we need to divide it into three parts (some of which might turn out empty)
// set pivot to the content of the first node
Type pivot_value = pivot -> info;
// go through all the nodes starting from the second;
// nodes whose 'info' == pivot go into the 'pivot' sublist;
// nodes whose 'info' > pivot go into the 'greater' sublist;
// nodes whose 'info' < pivot go into the 'smaller' sublist
bool greater_is_empty = true;
bool smaller_is_empty = true;
nodeType<Type>* current = pivot -> link;
nodeType<Type>* pivot_last = pivot;
nodeType<Type>* greater_last;
nodeType<Type>* smaller_last;
while (current != NULL){
if (current -> info == pivot_value){
pivot_last -> link = current;
pivot_last = current;
}
else if (current -> info > pivot_value){
// check to see if the 'greater' list is empty
if (greater_is_empty){
greater = current;
greater_last = current;
greater_is_empty = false;
}
else {
// if we're here, we know that the 'greater' list is not empty
greater_last -> link = current;
greater_last = current;
}
}
else { // current -> info < pivot_value
// check to see if the 'smaller' list is empty
if (smaller_is_empty){
smaller = current;
smaller_last = current;
smaller_is_empty = false;
}
else {
// if we're here, we know that the 'greater' list is not empty
smaller_last -> link = current;
smaller_last = current;
}
}
current = current -> link;
}
// if we're here, we're done with the list
// to finish off, we need to make sure that
// last nodes of all sublists don't point to anything
pivot_last -> link = NULL;
if (!greater_is_empty)
greater_last -> link = NULL;
if (!smaller_is_empty)
smaller_last -> link = NULL;
}
template <class Type>
nodeType<Type>* linkedListType<Type>::merge2(nodeType<Type>* first1, nodeType<Type>* first2){
// appends first2 to first 1
// check if the first list is empty
if (first1 == NULL)
return first2;
// check if the second list is empty
if (first2 == NULL)
return first1;
// if we're here, we know that both lists are non-empty
// find the last element of the of the first list
nodeType<Type>* last1 = first1;
while (last1 -> link != NULL)
last1 = last1 -> link;
// link the lists and return the pointer to the merged list
last1 -> link = first2;
return first1;
}
template <class Type>
nodeType<Type>* linkedListType<Type>::merge3(nodeType<Type>* pivot, nodeType<Type>* greater, nodeType<Type>* smaller){
// we assume that all 3 lists are sorted
// 'pivot' is always non-empty
// the other two can be empty
// return a pointer to the head of the merged list
nodeType<Type>* temp_head = merge2(smaller, pivot);
nodeType<Type>* head = merge2(temp_head, greater);
return head;
}
template <class Type>
void linkedListType<Type>::quickSortHelper(nodeType<Type>* &head){
// check to see if the list has more than one node
// if not, then nothing to do
if (head != NULL && head -> link != NULL){
nodeType<Type>* head2; // the greater elements
nodeType<Type>* head3; // the smaller elements
divide(head, head2, head3);
quickSortHelper(head2); // sort the greater
quickSortHelper(head3); // sort the smaller
head = merge3(head, head2, head3); // merge
}
}
template <class Type>
void linkedListType<Type>::quickSort(){
quickSortHelper(first);
if (first == NULL)
last = NULL;
else{
last = first;
while (last -> link != NULL)
last = last -> link;
}
}
|
