From 73eafb33f2098bbd06ddbacab14feda5d0508c22 Mon Sep 17 00:00:00 2001 From: Chris Koeritz Date: Sun, 1 Jan 2017 01:37:39 -0500 Subject: [PATCH] quick sort now working also --- infobase/fortunes.dat | 5 + nucleus/library/algorithms/sorts.h | 59 ++++--- .../library/tests_algorithms/test_sorts.cpp | 147 +++++++++++------- 3 files changed, 130 insertions(+), 81 deletions(-) diff --git a/infobase/fortunes.dat b/infobase/fortunes.dat index 3ab62637..78717fc0 100644 --- a/infobase/fortunes.dat +++ b/infobase/fortunes.dat @@ -42535,4 +42535,9 @@ regarding christmas cards... 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. +~ +Hope is not a strategy. +Luck is not a factor. +Fear is not an option. + -- James Cameron diff --git a/nucleus/library/algorithms/sorts.h b/nucleus/library/algorithms/sorts.h index 9a390cb9..55f959b0 100644 --- a/nucleus/library/algorithms/sorts.h +++ b/nucleus/library/algorithms/sorts.h @@ -16,9 +16,6 @@ // Please send updates for this code to: fred@gruntose.com -- Thanks, fred. ////////////// -#include -//temp! - namespace algorithms { /* @@ -95,8 +92,7 @@ namespace algorithms { * merges two sorted arrays into a single sorted array. */ template - basis::array merge(basis::array &first, basis::array &second, - bool reverse) + basis::array merge(basis::array &first, basis::array &second, bool reverse) { basis::array to_return; // operate until we've consumed both of the arrays. @@ -108,8 +104,7 @@ namespace algorithms { } 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]))) { + } 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); @@ -286,13 +281,8 @@ namespace algorithms { // 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) { - -//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. @@ -304,23 +294,48 @@ namespace algorithms { ////////////// + //! swaps the values in the array stored at positions a and b. template - void partition(type v[], int start, int end) + 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. + //! 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) + void inner_quick_sort(type v[], int start, int end, bool reverse) { - if (start >= end) { - // nothing to see here. - } else { + if (start < end) { // 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); + int pivot = partition(v, start, end, reverse); + inner_quick_sort(v, start, pivot, reverse); + inner_quick_sort(v, pivot + 1, end, reverse); } } @@ -333,7 +348,7 @@ namespace algorithms { template void quick_sort(type v[], int n, bool reverse = false) { - inner_quick_sort(v, n, 0, n - 1, reverse); + inner_quick_sort(v, 0, n - 1, reverse); } } // namespace. diff --git a/nucleus/library/tests_algorithms/test_sorts.cpp b/nucleus/library/tests_algorithms/test_sorts.cpp index 0edc61bb..e936a721 100644 --- a/nucleus/library/tests_algorithms/test_sorts.cpp +++ b/nucleus/library/tests_algorithms/test_sorts.cpp @@ -29,8 +29,7 @@ using namespace textual; using namespace timely; using namespace unit_test; -const int MAX_ELEMENTS = 30; -//1200 +const int MAX_ELEMENTS = 1200; const int MAX_VALUE = 28000; @@ -43,15 +42,19 @@ public: : application_shell() { } + DEFINE_CLASS_NAME("test_sorts") - ; int *populate_random_c_array(int size); basis::array populate_random_array(int size); + void rerandomize(int list[], int size); + bool verify_ascending(const int *list, int size); + bool verify_descending(const int *list, int size); - void test_shell_sort(int *list, int size); - void test_heap_sort(int *list, int size); - void test_merge_sort(basis::array &list); + void test_shell_sort(int size); + void test_heap_sort(int size); + void test_merge_sort(int size); + void test_quick_sort(int size); virtual int execute(); }; @@ -72,112 +75,138 @@ basis::array test_sorts::populate_random_array(int size) return to_return; } -//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::rerandomize(int list[], int size) +{ + for (int i = 0; i < size; i++) + list[i] = randomizer().inclusive(0, MAX_VALUE); +} -void test_sorts::test_shell_sort(int *list, int size) +bool test_sorts::verify_ascending(const int *list, int size) +{ + FUNCDEF("verify_ascending") + int last = list[0]; + for (int j = 1; j < size; j++) { + if (list[j] < last) return false; + last = list[j]; + } + return true; +} + +bool test_sorts::verify_descending(const int *list, int size) +{ + FUNCDEF("verify_descending") + int last = list[0]; + for (int j = 1; j < size; j++) { + if (list[j] > last) return false; + last = list[j]; + } + return true; +} + +void test_sorts::test_shell_sort(int size) { FUNCDEF("test_shell_sort"); + int *list = populate_random_c_array(size); + // 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]; - } + ASSERT_TRUE(verify_ascending(list, size), + "ordering check - list should be ordered at first check"); - // re-randomize the list. - for (int i = 0; i < size; i++) - list[i] = randomizer().inclusive(0, MAX_VALUE); + rerandomize(list, size); // 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]; - } + ASSERT_TRUE(verify_descending(list, size), + "ordering check - list should be ordered at second check"); // clean up now. delete[] list; } -void test_sorts::test_heap_sort(int *list, int size) +void test_sorts::test_heap_sort(int size) { FUNCDEF("test_heap_sort"); + int *list = populate_random_c_array(size); + // check a normal sort. heap_sort(list, size); + ASSERT_TRUE(verify_ascending(list, size), + "ordering check - list should be ordered at first check"); - 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); + rerandomize(list, size); // 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]; - } + ASSERT_TRUE(verify_descending(list, size), + "ordering check - list should be ordered at second check"); // clean up now. delete[] list; } -void test_sorts::test_merge_sort(basis::array &list) +void test_sorts::test_merge_sort(int size) { FUNCDEF("test_merge_sort"); + basis::array list = populate_random_array(size); + // 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]; - } + ASSERT_TRUE(verify_ascending(ret.access(), size), + "ordering check - list should be ordered at first check"); - // re-randomize the list. - for (int i = 0; i < list.length(); i++) - list[i] = randomizer().inclusive(0, MAX_VALUE); + rerandomize(list.access(), size); // check a reversed sort. ret = merge_sort(list, true); + ASSERT_TRUE(verify_descending(ret.access(), size), + "ordering check - list should be ordered at second check"); +} - 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]; - } +void test_sorts::test_quick_sort(int size) +{ + FUNCDEF("test_quick_sort"); + + int *list = populate_random_c_array(size); + + // check a normal sort. + quick_sort(list, size); + ASSERT_TRUE(verify_ascending(list, size), + "ordering check - list should be ordered at first check"); + +// LOG(a_sprintf("after quick sort: %s", dump_list(list, size).s())); + + rerandomize(list, size); + + // check a reversed sort. + quick_sort(list, size, true); + ASSERT_TRUE(verify_descending(list, size), + "ordering check - list should be ordered at second check"); + + // clean up now. + delete[] list; } + int test_sorts::execute() { FUNCDEF("execute"); int size = MAX_ELEMENTS; - test_shell_sort(populate_random_c_array(size), size); - - test_heap_sort(populate_random_c_array(size), size); + test_shell_sort(size); - basis::array testarray = populate_random_array(size); - test_merge_sort(testarray); + test_heap_sort(size); - // test_quick_sort(populate_random_array(size), size); + test_merge_sort(size); + test_quick_sort(size); return final_report(); } -- 2.34.1