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