052ecb24419bf262326115193d08acc0e4c78609
[feisty_meow.git] / nucleus / library / algorithms / sorts.h
1 #ifndef ASSORTED_SORTS_GROUP
2 #define ASSORTED_SORTS_GROUP
3
4 //////////////
5 // Name   : sorts
6 // Author : Chris Koeritz
7 //////////////
8 // Copyright (c) 1991-$now By Author.  This program is free software; you can
9 // redistribute it and/or modify it under the terms of the GNU General Public
10 // License as published by the Free Software Foundation:
11 //     http://www.gnu.org/licenses/gpl.html
12 // or under the terms of the GNU Library license:
13 //     http://www.gnu.org/licenses/lgpl.html
14 // at your preference.  Those licenses describe your legal rights to this
15 // software, and no other rights or warranties apply.
16 // Please send updates for this code to: fred@gruntose.com -- Thanks, fred.
17 //////////////
18
19 namespace algorithms {
20
21         /*
22          * general considerations:
23          *
24          * + Generic objects to be sorted must support comparison operators.
25          *
26          * + If the "reverse" flag is true, the arrays will be sorted in reverse order.
27          *   Reverse order here means "descending", such that array element i is always greater than or equal to array element i+1.
28          *   Normal order is "ascending", such that element i is always less than or equal to array element i+1.
29          *
30          */
31
32         //! dumps the contents of the list out, assuming that the type can be turned into an int.
33         template<class type>
34         basis::astring dump_list(type v[], int size)
35         {
36                 basis::astring ret;
37                 for (int i = 0; i < size; i++) {
38                         ret += basis::a_sprintf("%d ", (int)v[i]);
39                 }
40                 return ret;
41         }
42
43         //! shell sort algorithm.
44         /*!
45          * Sorts a C array of the "type" with "n" elements.
46          * Operates on the original array.
47          * Performs within O(n^2) time (depending on the gap size used).
48          * Algorithm is based on Kernighan and Ritchie's "The C Programming Language".
49          */
50         template<class type>
51         void shell_sort(type v[], int n, bool reverse = false)
52         {
53                 type temp;
54                 int gap, i, j;
55                 /* the gap sizes decrease quadratically(?).  they partition the array of
56                  * items that need to be sorted into first two groups, then four, then
57                  * eight, etc.  the inner loop iterates across each gap's worth of the array.
58                  */
59                 for (gap = n / 2; gap > 0; gap /= 2) {
60                         // the i indexed loop is the base for where the comparisons are made in
61                         // the j indexed loop.  it makes sure that each item past the edge of
62                         // the gap sized partition gets considered.
63                         for (i = gap; i < n; i++) {
64                                 // the j indexed loop looks at the values in our current gap and ensures
65                                 // that they are in sorted order.
66                                 if (!reverse) {
67                                         // normal ordering.
68                                         for (j = i - gap; j >= 0 && v[j] > v[j + gap]; j = j - gap) {
69                                                 // swap the elements that are disordered.
70                                                 temp = v[j];
71                                                 v[j] = v[j + gap];
72                                                 v[j + gap] = temp;
73                                         }
74                                 } else {
75                                         // reversed ordering.
76                                         for (j = i - gap; j >= 0 && v[j] < v[j + gap]; j = j - gap) {
77                                                 // swap the elements that are disordered.
78                                                 temp = v[j];
79                                                 v[j] = v[j + gap];
80                                                 v[j + gap] = temp;
81                                         }
82                                 }
83                         }
84                 }
85         }
86
87 //////////////
88
89         /*!
90          * sorted array merge
91          *
92          * merges two sorted arrays into a single sorted array.
93          */
94         template<class type>
95         basis::array<type> merge(basis::array<type> &first, basis::array<type> &second, bool reverse)
96         {
97                 basis::array<type> to_return;
98                 // operate until we've consumed both of the arrays.
99                 while ((first.length() > 0) || (second.length() > 0)) {
100                         if (first.length() <= 0) {
101                                 // nothing left in first, so use the second.
102                                 to_return += second[0];
103                                 second.zap(0, 0);
104                         } else if (second.length() <= 0) {
105                                 to_return += first[0];
106                                 first.zap(0, 0);
107                         } else if ((!reverse && (first[0] <= second[0])) || (reverse && (first[0] >= second[0]))) {
108                                 // the first list has a better value to add next.
109                                 to_return += first[0];
110                                 first.zap(0, 0);
111                         } else {
112                                 // the second list has a better value to add next.
113                                 to_return += second[0];
114                                 second.zap(0, 0);
115                         }
116                 }
117                 return to_return;
118         }
119
120         /*!
121          * merge sort
122          *
123          * operates in O(n log(n)) time.
124          * returns a new array with sorted data.
125          */
126         template<class type>
127         basis::array<type> merge_sort(const basis::array<type> &v, bool reverse = false)
128         {
129                 if (v.length() <= 1) {
130                         return basis::array<type>(v);
131                 }
132                 int midway = v.length() / 2;
133                 basis::array<type> firstPart = merge_sort(v.subarray(0, midway - 1), reverse);
134                 basis::array<type> secondPart = merge_sort(v.subarray(midway, v.length() - 1), reverse);
135                 return merge(firstPart, secondPart, reverse);
136         }
137
138 //////////////
139
140         /*!
141          * a heap is a structure that can quickly return the highest (or lowest) value,
142          * depending on how the priority of the item is defined.
143          * a "normal" heap keeps the highest element available first; a reverse sorted heap
144          * keeps the lowest element available first.
145          * restructuring the heap is fast, and is O(n log(n)).
146          * the implicit structure is a binary tree
147          * represented in a flat array, where the children of a node at position n are
148          * in positions n * 2 + 1 and n * 2 + 2 (zero based).
149          */
150 //hmmm: move this class out to basis?.
151         template<class type>
152         class heap
153         {
154         public:
155                 heap(type to_sort[], int n, bool reverse)
156                 {
157                         _total = n;
158                         _reverse = reverse;
159                         _heapspace = to_sort;
160                         heapify();
161                 }
162
163                 //! swaps the values in the heap stored at positions a and b.
164                 void swap_values(int a, int b)
165                 {
166                         type temp = _heapspace[a];
167                         _heapspace[a] = _heapspace[b];
168                         _heapspace[b] = temp;
169                 }
170
171                 //! get the index of the parent of the node at i.
172                 /*! this will not return the parent index of the root, since there is no parent. */
173                 int parent_index(int i)
174                 {
175                         return i / 2;  // rely on integer division to shave off remainder.
176                 }
177
178                 //! returns the left child of node at position i.
179                 int left_child(int i)
180                 {
181                         return 2 * i + 1;
182                 }
183
184                 //! returns the right child of node at position i.
185                 int right_child(int i)
186                 {
187                         return 2 * i + 2;
188                 }
189
190                 //! re-sorts the heapspace to maintain the heap ordering.
191                 void heapify()
192                 {
193                         int start = parent_index(_total - 1);
194                         // iterate from the back of the array towards the front, so depth-first.
195                         while (start >= 0) {
196                                 // sift down the node at the index 'start' such that all nodes below it are heapified.
197                                 sift_down(start, _total - 1);
198                                 start--;  // move the start upwards towards the root.
199                         }
200                 }
201
202                 void sift_down(int start, int end)
203                 {
204                         int root = start;
205
206                         // while the current root still has a kid...
207                         while (left_child(root) <= end) {
208                                 int child = left_child(root);
209                                 // figure out which child to swap with.
210                                 int swap = root;
211                                 // check if the root should be swapped with this kid.
212                                 if ((!_reverse && (_heapspace[swap] > _heapspace[child]))
213                                     || (_reverse && (_heapspace[swap] < _heapspace[child])))
214                                 {
215                                         swap = child;
216                                 }
217                                 // check if the other child should be swapped with the root or left kid.
218                                 if ((child + 1 <= end)
219                                     && ((!_reverse && (_heapspace[swap] > _heapspace[child + 1]))
220                                         || (_reverse && (_heapspace[swap] < _heapspace[child + 1]))))
221                                 {
222                                         swap = child + 1;
223                                 }
224                                 if (swap == root) {
225                                         // the root has the largest (or smallest) element, so we're done.
226                                         return;
227                                 } else {
228                                         swap_values(root, swap);
229                                         root = swap;
230                                         // repeat to continue sifting down the child now.
231                                 }
232                         }
233                 }
234
235                 //! re-sorts the heapspace to maintain the heap ordering.  this uses sift_up.
236                 void alt_heapify()
237                 {
238                         int end = 1;  // start at first child.
239
240                         while (end < _total) {
241                                 // sift down the node at the index 'start' such that all nodes below it are heapified.
242                                 sift_up(0, end++);
243                         }
244                 }
245
246                 //! start is how far up in the heap to sort.  end is the node to sift.
247                 void sift_up(int start, int end)
248                 {
249                         int child = end;
250                         // loop until we hit the starting node, where we're done.
251                         while (child > start) {
252                                 int parent = parent_index(child);
253                                 if ((!_reverse && (_heapspace[parent] < _heapspace[child]))
254                                     || (_reverse && (_heapspace[parent] > _heapspace[child])))
255                                 {
256                                         swap_values(parent, child);
257                                         child = parent;
258                                         // continue sifting at the parent now.
259                                 } else {
260                                         // done sorting.
261                                         return;
262                                 }
263                         }
264                 }
265
266         private:
267                 bool _reverse = false;  // is the sorting in reverse?
268                 int _total = 0;
269                 int *_heapspace = NULL_POINTER;
270         };
271
272         /*!
273          * heap sort
274          *
275          * operates in O(n log(n)).
276          * sorts the original array.
277          */
278         template<class type>
279         void heap_sort(type v[], int n, bool reverse = false)
280         {
281                 // reverse the sense of "reverse", since our algorithm expects a normal heap (with largest on top).
282                 heap<type> hap(v, n, !reverse);
283
284                 int end = n - 1;
285                 while (end > 0) {
286                         // a[0] is the root and largest value for a normal heap. The swap moves it to the real end of the list and takes it out of consideration.
287                         hap.swap_values(end, 0);
288                         // reduce the heap size by 1.
289                         end--;
290                         // that swap ruined the heap property, so re-heapify.
291                         hap.sift_down(0, end);
292                 }
293         }
294
295 //////////////
296
297         //! swaps the values in the array stored at positions a and b.
298         template<class type>
299         void swap_values(type array[], int a, int b)
300         {
301                 type temp = array[a];
302                 array[a] = array[b];
303                 array[b] = temp;
304         }
305
306         // hoare's partition implementation.
307         template<class type>
308         int partition(type a[], int start, int end, bool reverse)
309         {
310 //              printf("before partition: %s\n", dump_list(a + start, end - start + 1).s());
311                 int pivot = a[start];
312                 int i = start - 1;
313                 int j = end + 1;
314                 while (true) {
315                         do {
316                                 i++;
317                         } while ((!reverse && (a[i] < pivot)) || (reverse && (a[i] > pivot)));
318                         do {
319                                 j--;
320                         } while ((!reverse && (a[j] > pivot)) || (reverse && (a[j] < pivot)));
321
322                         if (i >= j) {
323 //                              printf("after partition: %s\n", dump_list(a + start, end - start + 1).s());
324                                 return j;
325                         }
326                         swap_values(a, i, j);
327                 }
328         }
329
330         //! the recursive version of quick sort that does the work for our convenience method.
331         template<class type>
332         void inner_quick_sort(type v[], int start, int end, bool reverse)
333         {
334                 if (start < end) {
335                         // figure out where to pivot, and sort both halves around the pivot index.
336                         int pivot = partition(v, start, end, reverse);
337                         inner_quick_sort(v, start, pivot, reverse);
338                         inner_quick_sort(v, pivot + 1, end, reverse);
339                 }
340         }
341
342         /*!
343          * quick sort
344          *
345          * operates in O(n log(n)) time on average, worst case O(n^2).
346          * sorts the original array.
347          */
348         template<class type>
349         void quick_sort(type v[], int n, bool reverse = false)
350         {
351                 inner_quick_sort(v, 0, n - 1, reverse);
352         }
353
354 }  // namespace.
355
356 #endif // outer guard.
357