X-Git-Url: https://feistymeow.org/gitweb/?a=blobdiff_plain;f=nucleus%2Flibrary%2Falgorithms%2Fsorts.h;fp=nucleus%2Flibrary%2Falgorithms%2Fsorts.h;h=c6e21abedc66ec69992016668e7e1ec51685db14;hb=7b39f7e279005c8466ef508220a532ce2aa4abf8;hp=0000000000000000000000000000000000000000;hpb=3fbd372b35b15a19fb171d5ae34294ff7b1e6485;p=feisty_meow.git diff --git a/nucleus/library/algorithms/sorts.h b/nucleus/library/algorithms/sorts.h new file mode 100644 index 00000000..c6e21abe --- /dev/null +++ b/nucleus/library/algorithms/sorts.h @@ -0,0 +1,374 @@ +#ifndef ASSORTED_SORTS_GROUP +#define ASSORTED_SORTS_GROUP + +////////////// +// Name : sorts +// Author : Chris Koeritz +////////////// +// Copyright (c) 1991-$now By Author. This program is free software; you can +// redistribute it and/or modify it under the terms of the GNU General Public +// License as published by the Free Software Foundation: +// http://www.gnu.org/licenses/gpl.html +// or under the terms of the GNU Library license: +// http://www.gnu.org/licenses/lgpl.html +// at your preference. Those licenses describe your legal rights to this +// software, and no other rights or warranties apply. +// Please send updates for this code to: fred@gruntose.com -- Thanks, fred. +////////////// + +#include + +namespace algorithms { + + /* + * general considerations: + * + * + Generic objects to be sorted must support comparison operators. + * + * + If the "reverse" flag is true, the arrays will be sorted in reverse order. + * Reverse order here means "descending", such that array element i is always greater than or equal to array element i+1. + * Normal order is "ascending", such that element i is always less than or equal to array element i+1. + * + */ + + //! dumps the contents of the list out, assuming that the type can be turned into an int. + template + basis::astring dump_list(type v[], int size) + { + basis::astring ret; + for (int i = 0; i < size; i++) { + ret += basis::a_sprintf("%d ", (int)v[i]); + } + return ret; + } + + //! shell sort algorithm. + /*! + * Sorts a C array of the "type" with "n" elements. + * Operates on the original array. + * Performs within O(n^2) time (depending on the gap size used). + * Algorithm is based on Kernighan and Ritchie's "The C Programming Language". + */ + template + void shell_sort(type v[], int n, bool reverse = false) + { + type temp; + int gap, i, j; + /* the gap sizes decrease quadratically(?). they partition the array of + * items that need to be sorted into first two groups, then four, then + * eight, etc. the inner loop iterates across each gap's worth of the array. + */ + for (gap = n / 2; gap > 0; gap /= 2) { + // the i indexed loop is the base for where the comparisons are made in + // the j indexed loop. it makes sure that each item past the edge of + // the gap sized partition gets considered. + for (i = gap; i < n; i++) { + // the j indexed loop looks at the values in our current gap and ensures + // that they are in sorted order. + if (!reverse) { + // normal ordering. + for (j = i - gap; j >= 0 && v[j] > v[j + gap]; j = j - gap) { + // swap the elements that are disordered. + temp = v[j]; + v[j] = v[j + gap]; + v[j + gap] = temp; + } + } else { + // reversed ordering. + for (j = i - gap; j >= 0 && v[j] < v[j + gap]; j = j - gap) { + // swap the elements that are disordered. + temp = v[j]; + v[j] = v[j + gap]; + v[j + gap] = temp; + } + } + } + } + } + +////////////// + + /*! + * sorted array merge + * + * merges two sorted arrays into a single sorted array. + */ + template + basis::array merge(basis::array &first, basis::array &second, bool reverse) + { + basis::array to_return; + // operate until we've consumed both of the arrays. + while ((first.length() > 0) || (second.length() > 0)) { + if (first.length() <= 0) { + // nothing left in first, so use the second. + to_return += second[0]; + second.zap(0, 0); + } else if (second.length() <= 0) { + to_return += first[0]; + first.zap(0, 0); + } else if ((!reverse && (first[0] <= second[0])) || (reverse && (first[0] >= second[0]))) { + // the first list has a better value to add next. + to_return += first[0]; + first.zap(0, 0); + } else { + // the second list has a better value to add next. + to_return += second[0]; + second.zap(0, 0); + } + } + return to_return; + } + + /*! + * merge sort + * + * operates in O(n log(n)) time. + * returns a new array with sorted data. + */ + template + basis::array merge_sort(const basis::array &v, bool reverse = false) + { + if (v.length() <= 1) { + return basis::array(v); + } + int midway = v.length() / 2; + basis::array firstPart = merge_sort(v.subarray(0, midway - 1), reverse); + basis::array secondPart = merge_sort(v.subarray(midway, v.length() - 1), reverse); + return merge(firstPart, secondPart, reverse); + } + +////////////// + + /*! + * a heap is a structure that can quickly return the highest (or lowest) value, + * depending on how the priority of the item is defined. + * a "normal" heap keeps the highest element available first; a reverse sorted heap + * keeps the lowest element available first. + * restructuring the heap is fast, and is O(n log(n)). + * the implicit structure is a binary tree + * represented in a flat array, where the children of a node at position n are + * in positions n * 2 + 1 and n * 2 + 2 (zero based). + */ +//hmmm: move this class out to basis?. + template + class heap + { + public: + heap(type to_sort[], int n, bool reverse) + { + _total = n; + _reverse = reverse; + _heapspace = to_sort; + heapify(); + } + + //! swaps the values in the heap stored at positions a and b. + void swap_values(int a, int b) + { + type temp = _heapspace[a]; + _heapspace[a] = _heapspace[b]; + _heapspace[b] = temp; + } + + //! get the index of the parent of the node at i. + /*! this will not return the parent index of the root, since there is no parent. */ + int parent_index(int i) + { + return i / 2; // rely on integer division to shave off remainder. + } + + //! returns the left child of node at position i. + int left_child(int i) + { + return 2 * i + 1; + } + + //! returns the right child of node at position i. + int right_child(int i) + { + return 2 * i + 2; + } + + //! re-sorts the heapspace to maintain the heap ordering. + void heapify() + { + int start = parent_index(_total - 1); + // iterate from the back of the array towards the front, so depth-first. + while (start >= 0) { + // sift down the node at the index 'start' such that all nodes below it are heapified. + sift_down(start, _total - 1); + start--; // move the start upwards towards the root. + } + } + + void sift_down(int start, int end) + { + int root = start; + + // while the current root still has a kid... + while (left_child(root) <= end) { + int child = left_child(root); + // figure out which child to swap with. + int swap = root; + // check if the root should be swapped with this kid. + if ((!_reverse && (_heapspace[swap] > _heapspace[child])) + || (_reverse && (_heapspace[swap] < _heapspace[child]))) + { + swap = child; + } + // check if the other child should be swapped with the root or left kid. + if ((child + 1 <= end) + && ((!_reverse && (_heapspace[swap] > _heapspace[child + 1])) + || (_reverse && (_heapspace[swap] < _heapspace[child + 1])))) + { + swap = child + 1; + } + if (swap == root) { + // the root has the largest (or smallest) element, so we're done. + return; + } else { + swap_values(root, swap); + root = swap; + // repeat to continue sifting down the child now. + } + } + } + + //! re-sorts the heapspace to maintain the heap ordering. this uses sift_up. + void alt_heapify() + { + int end = 1; // start at first child. + + while (end < _total) { + // sift down the node at the index 'start' such that all nodes below it are heapified. + sift_up(0, end++); + } + } + + //! start is how far up in the heap to sort. end is the node to sift. + void sift_up(int start, int end) + { + int child = end; + // loop until we hit the starting node, where we're done. + while (child > start) { + int parent = parent_index(child); + if ((!_reverse && (_heapspace[parent] < _heapspace[child])) + || (_reverse && (_heapspace[parent] > _heapspace[child]))) + { + swap_values(parent, child); + child = parent; + // continue sifting at the parent now. + } else { + // done sorting. + return; + } + } + } + + private: + bool _reverse; // is the sorting in reverse? + int _total; // how many total elements are there? + int *_heapspace; // track a pointer to the array. + }; + + /*! + * heap sort + * + * operates in O(n log(n)). + * sorts the original array. + */ + template + void heap_sort(type v[], int n, bool reverse = false) + { + // reverse the sense of "reverse", since our algorithm expects a normal heap (with largest on top). + heap hap(v, n, !reverse); + + int end = n - 1; + while (end > 0) { + // 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. + hap.swap_values(end, 0); + // reduce the heap size by 1. + end--; + // that swap ruined the heap property, so re-heapify. + hap.sift_down(0, end); + } + } + +////////////// + + //! swaps the values in the array stored at positions a and b. + template + void swap_values(type array[], int a, int b) + { + type temp = array[a]; + array[a] = array[b]; + array[b] = temp; + } + + // hoare's partition implementation. + template + int partition(type a[], int start, int end, bool reverse) + { +// printf("before partition: %s\n", dump_list(a + start, end - start + 1).s()); + int pivot = a[start]; + int i = start - 1; + int j = end + 1; + while (true) { + do { + i++; + } while ((!reverse && (a[i] < pivot)) || (reverse && (a[i] > pivot))); + do { + j--; + } while ((!reverse && (a[j] > pivot)) || (reverse && (a[j] < pivot))); + + if (i >= j) { +// printf("after partition: %s\n", dump_list(a + start, end - start + 1).s()); + return j; + } + swap_values(a, i, j); + } + } + + //! the recursive version of quick sort that does the work for our convenience method. + template + void inner_quick_sort(type v[], int start, int end, bool reverse) + { + if (start < end) { + // figure out where to pivot, and sort both halves around the pivot index. + int pivot = partition(v, start, end, reverse); + inner_quick_sort(v, start, pivot, reverse); + inner_quick_sort(v, pivot + 1, end, reverse); + } + } + + /*! + * quick sort + * + * operates in O(n log(n)) time on average, worst case O(n^2). + * sorts the original array. + */ + template + void quick_sort(type v[], int n, bool reverse = false) + { + inner_quick_sort(v, 0, n - 1, reverse); + } + + ////////////// + + //! handy method for randomizing the order of a list. not strictly a sorting function... + template + void randomize_list(type v[], int n) + { + mathematics::chaos randomizer; + for (int i = 0; i < n; i++) { + // we will swap with any element that is not prior to the current index; thus we allow + // swapping the element with itself and later, but not with anything earlier. + int swap_index = randomizer.inclusive(i, n - 1); + swap_values(v, i, swap_index); + } + } + +} // namespace. + +#endif // outer guard. +