1 #ifndef ASSORTED_SORTS_GROUP
2 #define ASSORTED_SORTS_GROUP
6 // Author : Chris Koeritz
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.
22 namespace algorithms {
25 * general considerations:
27 * + Generic objects to be sorted must support comparison operators.
29 * + If the "reverse" flag is true, the arrays will be sorted in reverse order.
30 * Reverse order here means "descending", such that array element i is always greater than or equal to array element i+1.
31 * Normal order is "ascending", such that element i is always less than or equal to array element i+1.
35 //! dumps the contents of the list out, assuming that the type can be turned into an int.
37 basis::astring dump_list(type v[], int size)
40 for (int i = 0; i < size; i++) {
41 ret += basis::a_sprintf("%d ", (int)v[i]);
46 //! shell sort algorithm.
48 * Sorts a C array of the "type" with "n" elements.
49 * Operates on the original array.
50 * Performs in O(n log(n)) time.
51 * Algorithm is based on Kernighan and Ritchie's "The C Programming Language".
54 void shell_sort(type v[], int n, bool reverse = false)
58 /* the gap sizes decrease quadratically(?). they partition the array of
59 * items that need to be sorted into first two groups, then four, then
60 * eight, etc. the inner loop iterates across each gap's worth of the array.
62 for (gap = n / 2; gap > 0; gap /= 2) {
63 // the i indexed loop is the base for where the comparisons are made in
64 // the j indexed loop. it makes sure that each item past the edge of
65 // the gap sized partition gets considered.
66 for (i = gap; i < n; i++) {
67 // the j indexed loop looks at the values in our current gap and ensures
68 // that they are in sorted order.
71 for (j = i - gap; j >= 0 && v[j] > v[j + gap]; j = j - gap) {
72 // swap the elements that are disordered.
79 for (j = i - gap; j >= 0 && v[j] < v[j + gap]; j = j - gap) {
80 // swap the elements that are disordered.
95 * merges two sorted arrays into a single sorted array.
98 basis::array<type> merge(basis::array<type> &first, basis::array<type> &second,
101 basis::array<type> to_return;
102 // operate until we've consumed both of the arrays.
103 while ((first.length() > 0) || (second.length() > 0)) {
104 if (first.length() <= 0) {
105 // nothing left in first, so use the second.
106 to_return += second[0];
108 } else if (second.length() <= 0) {
109 to_return += first[0];
111 } else if ( (!reverse && (first[0] <= second[0]))
112 || (reverse && (first[0] >= second[0]))) {
113 // the first list has a better value to add next.
114 to_return += first[0];
117 // the second list has a better value to add next.
118 to_return += second[0];
128 * operates in O(n log(n)) time.
129 * returns a new array with sorted data.
132 basis::array<type> merge_sort(const basis::array<type> &v, bool reverse = false)
134 if (v.length() <= 1) {
135 return basis::array<type>(v);
137 int midway = v.length() / 2;
138 basis::array<type> firstPart = merge_sort(v.subarray(0, midway - 1), reverse);
139 basis::array<type> secondPart = merge_sort(v.subarray(midway, v.length() - 1), reverse);
140 return merge(firstPart, secondPart, reverse);
146 * a heap is a structure that can quickly return the highest (or lowest) value,
147 * depending on how the priority of the item is defined.
148 * a "normal" heap keeps the highest element available first; a reverse sorted heap
149 * keeps the lowest element available first.
150 * restructuring the heap is fast, and is O(n log(n)).
151 * the implicit structure is a binary tree
152 * represented in a flat array, where the children of a node at position n are
153 * in positions n * 2 + 1 and n * 2 + 2 (zero based).
155 //hmmm: move this class out to basis?.
160 heap(type to_sort[], int n, bool reverse)
164 _heapspace = to_sort;
168 //! swaps the values in the heap stored at positions a and b.
169 void swap_values(int a, int b)
171 type temp = _heapspace[a];
172 _heapspace[a] = _heapspace[b];
173 _heapspace[b] = temp;
176 //! get the index of the parent of the node at i.
177 /*! this will not return the parent index of the root, since there is no parent. */
178 int parent_index(int i)
180 return i / 2; // rely on integer division to shave off remainder.
183 //! returns the left child of node at position i.
184 int left_child(int i)
189 //! returns the right child of node at position i.
190 int right_child(int i)
195 //! re-sorts the heapspace to maintain the heap ordering.
198 int start = parent_index(_total - 1);
199 // iterate from the back of the array towards the front, so depth-first.
201 // sift down the node at the index 'start' such that all nodes below it are heapified.
202 sift_down(start, _total - 1);
203 start--; // move the start upwards towards the root.
207 void sift_down(int start, int end)
211 // while the current root still has a kid...
212 while (left_child(root) <= end) {
213 int child = left_child(root);
214 // figure out which child to swap with.
216 // check if the root should be swapped with this kid.
217 if ((!_reverse && (_heapspace[swap] > _heapspace[child]))
218 || (_reverse && (_heapspace[swap] < _heapspace[child])))
222 // check if the other child should be swapped with the root or left kid.
223 if ((child + 1 <= end)
224 && ((!_reverse && (_heapspace[swap] > _heapspace[child + 1]))
225 || (_reverse && (_heapspace[swap] < _heapspace[child + 1]))))
230 // the root has the largest (or smallest) element, so we're done.
233 swap_values(root, swap);
235 // repeat to continue sifting down the child now.
240 //! re-sorts the heapspace to maintain the heap ordering. this uses sift_up.
243 int end = 1; // start at first child.
245 while (end < _total) {
246 // sift down the node at the index 'start' such that all nodes below it are heapified.
251 //! start is how far up in the heap to sort. end is the node to sift.
252 void sift_up(int start, int end)
255 // loop until we hit the starting node, where we're done.
256 while (child > start) {
257 int parent = parent_index(child);
258 if ((!_reverse && (_heapspace[parent] < _heapspace[child]))
259 || (_reverse && (_heapspace[parent] > _heapspace[child])))
261 swap_values(parent, child);
263 // continue sifting at the parent now.
272 bool _reverse = false; // is the sorting in reverse?
274 int *_heapspace = NULL_POINTER;
280 * operates in O(n log(n)).
281 * sorts the original array.
284 void heap_sort(type v[], int n, bool reverse = false)
286 // reverse the sense of "reverse", since our algorithm expects a normal heap (with largest on top).
287 heap<type> hap(v, n, !reverse);
290 // printf("hey after heaping: %s\n", dump_list(v, n).s());
295 //printf("moving value %d\n", (int)v[0]);
296 // 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.
297 hap.swap_values(end, 0);
298 // reduce the heap size by 1.
300 // that swap ruined the heap property, so re-heapify.
301 hap.sift_down(0, end);
308 void partition(type v[], int start, int end)
313 //! the recursive version of quick sort that does the work for our convenience method.
315 void inner_quick_sort(type v[], int n, int start, int end, bool reverse = false)
318 // nothing to see here.
320 // figure out where to pivot, and sort both halves around the pivot index.
321 int pivot = partition(v, start, end);
322 quicksort(v, start, pivot - 1);
323 quicksort(v, pivot + 1, end);
330 * operates in O(n log(n)) time on average, worst case O(n^2).
331 * sorts the original array.
334 void quick_sort(type v[], int n, bool reverse = false)
336 inner_quick_sort(v, n, 0, n - 1, reverse);
341 #endif // outer guard.