From 0cc8bcdf18d075ad1297a054e571570e75624e84 Mon Sep 17 00:00:00 2001 From: Chris Koeritz Date: Sat, 31 Dec 2016 23:00:39 -0500 Subject: [PATCH] working merge and heap sorts --- infobase/fortunes.dat | 82 ++- nucleus/library/algorithms/sorts.h | 465 +++++++++++------- .../library/tests_algorithms/test_sorts.cpp | 179 ++++--- 3 files changed, 482 insertions(+), 244 deletions(-) diff --git a/infobase/fortunes.dat b/infobase/fortunes.dat index 22f958e3..3ab62637 100644 --- a/infobase/fortunes.dat +++ b/infobase/fortunes.dat @@ -42447,24 +42447,6 @@ five strengths are practiced: the strength of wisdom awareness. -- Gampopa, in "The Jewel Ornament of Liberation", published by Shambhala Publications -~ - Your eggnog to rum ratio should be 23% to 77%. I would then spice the -eggnog with nutmeg and use more than you're comfortable with because sailors -used to use it as [a] hallucinogen... - Also, enter on a reindeer. And if you enter on a reindeer, stay on the -reindeer. And if you can’t reach something because you’re too high up -sitting on the reindeer, just ask for help. That goes for life, too. Don’t -be afraid to ask for help and stay on that reindeer. - -- T.J. Miller’s recipe for the perfect holiday party -~ -if you can't beat them, join them, and subvert them from the inside. - -- fred t. hamster -~ -regarding christmas cards... -"i would create my own as a desktop publishing activity, with all new current -stuff. but it's way too much effort. basically, i can either give you a -present or make you a card. which do you prefer?" - -- thus spake slackathustra. ~ III. Path of Insight @@ -42489,4 +42471,68 @@ of the branches of enlightenment: the perfect equanimity branch. -- The Jewel Ornament of Liberation, by Gampopa, published by Shambhala Publications +~ +IV. Path of Meditation + +The path of meditation practice begins after the realization of special +insight. It has two paths: + A. the path of worldly meditation practice and + B. the path of meditation practice beyond the world. +A. + Worldly Meditation Practice consists of the first, second, third, and +fourth meditative stages, and the formless stages of increasing the infinite +nature of space, increasing the infinity of consciousness, increasing the +nothing-whatsoever-ness, and increasing neither perception nor non-perception. +There are three purposes to practicing this meditation: + ++ suppressing the afflicting emotions which are the subject of +abandonment in the path of meditation; ++ establishing the special qualities of the Four Immeasurables and so +forth; and ++ creating the foundation for the path beyond the world. + +B. + Meditation Practice Beyond the World consists of the furthering of calm +abiding and special insight, focused on the two types of wisdom. During the +path of insight there were two “patient acceptances” and two +“awarenesses” corresponding to each of the Four Noble Truths, making a +total of sixteen. The eight patient acceptances were completed in the path of +insight. One becomes familiarized with the eight awarenesses in the path of +meditation through the calm abiding and special insight related to the four +meditative concentrations and three of the formless absorptions. Furthermore, +part of the awareness of phenomena is to familiarize oneself with all the +realization of dharma-as-such. Part of the continuity awareness is to +familiarize oneself with all the realization of primordial wisdom. The state +of neither perception nor non-perception is merely worldly meditation because +the movement of sensation is so unclear. + Why is this called the path of meditation? Because there, one becomes +familiar with the realizations that one achieved in the path of insight. At +this stage, there are eight of the thirty-seven branches of enlightenment: + ++ perfect view, ++ perfect conception, perfect speech, perfect action, ++ perfect livelihood, ++ perfect effort, ++ perfect mindfulness, and ++ perfect absorption. + -- Gampopa, from "The Jewel Ornament of Liberation", published by Shambhala +Publications +~ + Your eggnog to rum ratio should be 23% to 77%. I would then spice the +eggnog with nutmeg and use more than you're comfortable with because sailors +used to use it as [a] hallucinogen... + Also, enter on a reindeer. And if you enter on a reindeer, stay on the +reindeer. And if you can’t reach something because you’re too high up +sitting on the reindeer, just ask for help. That goes for life, too. Don’t +be afraid to ask for help and stay on that reindeer. + -- T.J. Miller’s recipe for the perfect holiday party +~ +if you can't beat them, join them, and subvert them from the inside. + -- fred t. hamster +~ +regarding christmas cards... +"i would create my own as a desktop publishing activity, with all new current +stuff. but it's way too much effort. basically, i can either give you a +present or make you a card. which do you prefer?" + -- thus spake slackathustra. diff --git a/nucleus/library/algorithms/sorts.h b/nucleus/library/algorithms/sorts.h index dae0ca47..9a390cb9 100644 --- a/nucleus/library/algorithms/sorts.h +++ b/nucleus/library/algorithms/sorts.h @@ -16,202 +16,327 @@ // Please send updates for this code to: fred@gruntose.com -- Thanks, fred. ////////////// +#include +//temp! + 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. - * - */ - -//! shell sort algorithm. -/*! - * Sorts a C array of the "type" with "n" elements. - * Operates on the original array. - * Performs in O(n log(n)) time. - * 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. + /* + * 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. + * */ - 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(const basis::array &first, basis::array &second, bool reverse) -{ - int first_iter = 0; - int second_iter = 0; - //hmmm: careful below; remember differences in heap allocated objects versus new-ed ones. - //this might be really inefficient to return on stack..? - basis::array to_return; - // operate until we've consumed both of the arrays. - while ((first_iter < first.length()) && (second_iter < second.length())) { - if ( (!reverse && (first[first_iter] <= second[second_iter])) - || (reverse && (first[first_iter] >= second[second_iter])) ) { - // next item from first array goes into the merged array next. - to_return += first[first_iter++]; - } else { - // next item from second array goes into the merged array next. - to_return += second[second_iter++]; + //! 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; } - 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 new basis::array(v); + + //! shell sort algorithm. + /*! + * Sorts a C array of the "type" with "n" elements. + * Operates on the original array. + * Performs in O(n log(n)) time. + * 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; + } + } + } + } } - int midway = v.length() / 2; - basis::array firstPart = merge_sort(v.subarray(0, midway - 1)); - basis::array secondPart = merge_sort(v.subarray(midway, v.length() - 1)); - 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. restructuring is - * also fast, when new data are added. 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(int max_elements, bool reverse) { - _max_elements = max_elements; - _reverse = reverse; - _heapspace = new basis::array (_max_elements); + /*! + * 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; } - virtual ~heap() { - WHACK(_heapspace); + /*! + * 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); } - //! swaps the values in the heap stored at positions a and b. - void swap(int a, int b) +////////////// + + /*! + * 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 { - type temp = _heapspace[a]; - _heapspace[a] = _heapspace[b]; - _heapspace[b] = temp; - } + 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; + } - //! re-sorts the heapspace to maintain the heap ordering. - void heapify() + //! 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 = false; // is the sorting in reverse? + int _total = 0; + int *_heapspace = NULL_POINTER; + }; + + /*! + * 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); - } + //temp +// printf("hey after heaping: %s\n", dump_list(v, n).s()); + + int end = n - 1; + while (end > 0) { - void add(type to_add) { - // - } - - -private: - int _max_elements; - bool _reverse; - basis::array *_heapspace = NULL_POINTER; -}; - -/*! - * heap sort - * - * operates in O(n log(n)). - * sorts the original array. - */ -template -void heap_sort(type v[], int n, bool reverse = false) -{ - // use heap. do sorty. -} +//printf("moving value %d\n", (int)v[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); + } + } ////////////// -template -void partition(type v[], int start, int end) -{ + template + void partition(type v[], int start, int end) + { -} + } //! the recursive version of quick sort that does the work for our convenience method. -template -void inner_quick_sort(type v[], int n, int start, int end, bool reverse = false) -{ - if (start >= end) { - // nothing to see here. - } else { - // figure out where to pivot, and sort both halves around the pivot index. - int pivot = partition(v, start, end); - quicksort(v, start, pivot - 1); - quicksort(v, pivot + 1, end); + template + void inner_quick_sort(type v[], int n, int start, int end, bool reverse = false) + { + if (start >= end) { + // nothing to see here. + } else { + // figure out where to pivot, and sort both halves around the pivot index. + int pivot = partition(v, start, end); + quicksort(v, start, pivot - 1); + quicksort(v, pivot + 1, end); + } } -} - -/*! - * 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, n, 0, n-1, reverse); -} - -} // namespace. + + /*! + * 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, n, 0, n - 1, reverse); + } + +} // namespace. #endif // outer guard. diff --git a/nucleus/library/tests_algorithms/test_sorts.cpp b/nucleus/library/tests_algorithms/test_sorts.cpp index 9cec59a3..0edc61bb 100644 --- a/nucleus/library/tests_algorithms/test_sorts.cpp +++ b/nucleus/library/tests_algorithms/test_sorts.cpp @@ -1,14 +1,14 @@ /* -* Name : test_sorts -* Author : Chris Koeritz -** -* Copyright (c) 1992-$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; either version 2 of * -* the License or (at your option) any later version. This is online at: * -* http://www.fsf.org/copyleft/gpl.html * -* Please send any updates to: fred@gruntose.com * -*/ + * Name : test_sorts + * Author : Chris Koeritz + ** + * Copyright (c) 1992-$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; either version 2 of * + * the License or (at your option) any later version. This is online at: * + * http://www.fsf.org/copyleft/gpl.html * + * Please send any updates to: fred@gruntose.com * + */ #include #include @@ -29,7 +29,8 @@ using namespace textual; using namespace timely; using namespace unit_test; -const int MAX_ELEMENTS = 1200; +const int MAX_ELEMENTS = 30; +//1200 const int MAX_VALUE = 28000; @@ -38,14 +39,21 @@ const int MAX_VALUE = 28000; class test_sorts : virtual public unit_base, virtual public application_shell { public: - test_sorts() : application_shell() {} - DEFINE_CLASS_NAME("test_sorts"); + test_sorts() + : application_shell() + { + } + DEFINE_CLASS_NAME("test_sorts") + ; - int *populate_random_c_array(int size); - basis::array populate_random_array(int size); - int test_shell_sort(int *list, int size); + int *populate_random_c_array(int size); + basis::array populate_random_array(int size); - virtual int execute(); + void test_shell_sort(int *list, int size); + void test_heap_sort(int *list, int size); + void test_merge_sort(basis::array &list); + + virtual int execute(); }; int *test_sorts::populate_random_c_array(int size) @@ -64,56 +72,115 @@ basis::array test_sorts::populate_random_array(int size) return to_return; } -int test_sorts::test_shell_sort(int *list, int size) +//hmmm: this pattern is very silly. it's nearly cookie cutter, so why not implement a templated version? +// one diff is the C array versus basis array usage. + +void test_sorts::test_shell_sort(int *list, int size) +{ + FUNCDEF("test_shell_sort"); + + // check a normal sort. + shell_sort(list, size); + int last = -1; + for (int j = 0; j < size; j++) { + ASSERT_FALSE(list[j] < last, "ordering check - list should be ordered at first check"); + last = list[j]; + } + + // re-randomize the list. + for (int i = 0; i < size; i++) + list[i] = randomizer().inclusive(0, MAX_VALUE); + + // check a reversed sort. + shell_sort(list, size, true); + last = MAX_VALUE + 100; // past the maximum we'll include in the list. + for (int j = 0; j < size; j++) { + ASSERT_FALSE(list[j] > last, "ordering check - list should be ordered at second check"); + last = list[j]; + } + + // clean up now. + delete[] list; +} + +void test_sorts::test_heap_sort(int *list, int size) +{ + FUNCDEF("test_heap_sort"); + + // check a normal sort. + heap_sort(list, size); + + int last = -1; + for (int j = 0; j < size; j++) { + ASSERT_FALSE(list[j] < last, "ordering check - list should be ordered at first check"); + last = list[j]; + } + + // re-randomize the list. + for (int i = 0; i < size; i++) + list[i] = randomizer().inclusive(0, MAX_VALUE); + + // check a reversed sort. + heap_sort(list, size, true); + + last = MAX_VALUE + 100; // past the maximum we'll include in the list. + for (int j = 0; j < size; j++) { + ASSERT_FALSE(list[j] > last, "ordering check - list should be ordered at second check"); + last = list[j]; + } + + // clean up now. + delete[] list; +} + +void test_sorts::test_merge_sort(basis::array &list) { - FUNCDEF("test_shell_sort"); - - // check a normal sort. - shell_sort(list, size); - int last = -1; - for (int j = 0; j < size; j++) { - ASSERT_FALSE(list[j] < last, "ordering check - list should be ordered at first check"); - last = list[j]; - } - - // re-randomize the list. - for (int i = 0; i < size; i++) - list[i] = randomizer().inclusive(0, MAX_VALUE); - - // check a reversed sort. - shell_sort(list, size, true); - last = MAX_VALUE + 100; // past the maximum we'll include in the list. - for (int j = 0; j < size; j++) { - ASSERT_FALSE(list[j] > last, "ordering check - list should be ordered at second check"); - last = list[j]; - } - - // clean up now. - delete [] list; - - //hmmm: wait, what if it fails above? - return true; + FUNCDEF("test_merge_sort"); + + // check a normal sort. + basis::array ret = merge_sort(list); + +// LOG(a_sprintf("list has %d elems", ret.length())); +// LOG(astring("list has ") + dump_list(ret.observe(), ret.length())); + + int last = -1; + for (int j = 0; j < list.length(); j++) { + ASSERT_FALSE(ret[j] < last, "ordering check - list should be ordered at first check"); + last = ret[j]; + } + + // re-randomize the list. + for (int i = 0; i < list.length(); i++) + list[i] = randomizer().inclusive(0, MAX_VALUE); + + // check a reversed sort. + ret = merge_sort(list, true); + + last = MAX_VALUE + 100; // past the maximum we'll include in the list. + for (int j = 0; j < list.length(); j++) { + ASSERT_FALSE(ret[j] > last, "ordering check - list should be ordered at second check"); + last = ret[j]; + } } int test_sorts::execute() { - FUNCDEF("execute"); + FUNCDEF("execute"); + + int size = MAX_ELEMENTS; - int size = MAX_ELEMENTS; + test_shell_sort(populate_random_c_array(size), size); -//astring ret; -//for (int i = 0; i < size; i++) ret += a_sprintf("%d ", list[i]); -//LOG(ret); -//LOG("-------------"); + test_heap_sort(populate_random_c_array(size), size); - test_shell_sort(populate_random_c_array(size), size); + basis::array testarray = populate_random_array(size); + test_merge_sort(testarray); -// test_quick_sort(populate_random_list(size), size); + // test_quick_sort(populate_random_array(size), size); -// test_merge_sort(populate_random_array(size)); - return final_report(); + return final_report(); } -HOOPLE_MAIN(test_sorts, ) +HOOPLE_MAIN(test_sorts,) -- 2.34.1