From daec747ca024ed7e5fbd19ab390c6eaeac2a3737 Mon Sep 17 00:00:00 2001 From: Chris Koeritz Date: Sun, 1 Jan 2017 15:39:19 -0500 Subject: [PATCH] tasty cakes renaming and cleaning fixed stupid placeholder file by using it as an anchor for the sorts methods instead. added an efficient randomize list method in sorts. using new randomize list method in sorts tester, removing yet more code. mmmm. --- nucleus/library/algorithms/placeholder.cpp | 8 -------- nucleus/library/algorithms/sorts.cpp | 2 ++ nucleus/library/algorithms/sorts.h | 19 +++++++++++++++++- .../library/tests_algorithms/test_sorts.cpp | 20 +++++++++---------- .../tests_nodes/test_singly_linked_list.cpp | 2 +- 5 files changed, 31 insertions(+), 20 deletions(-) delete mode 100644 nucleus/library/algorithms/placeholder.cpp create mode 100644 nucleus/library/algorithms/sorts.cpp diff --git a/nucleus/library/algorithms/placeholder.cpp b/nucleus/library/algorithms/placeholder.cpp deleted file mode 100644 index 953ca62c..00000000 --- a/nucleus/library/algorithms/placeholder.cpp +++ /dev/null @@ -1,8 +0,0 @@ - - -// sole purpose of this is to make the lib be generated, -// even though we currently do not have any code that lives inside it. - -int __private_private_bogus_placeholder_xj27_qx19() { return 32; } - - diff --git a/nucleus/library/algorithms/sorts.cpp b/nucleus/library/algorithms/sorts.cpp new file mode 100644 index 00000000..dc964a5a --- /dev/null +++ b/nucleus/library/algorithms/sorts.cpp @@ -0,0 +1,2 @@ + +#include "sorts.h" diff --git a/nucleus/library/algorithms/sorts.h b/nucleus/library/algorithms/sorts.h index 052ecb24..592f9903 100644 --- a/nucleus/library/algorithms/sorts.h +++ b/nucleus/library/algorithms/sorts.h @@ -16,6 +16,8 @@ // Please send updates for this code to: fred@gruntose.com -- Thanks, fred. ////////////// +#include + namespace algorithms { /* @@ -345,12 +347,27 @@ namespace algorithms { * operates in O(n log(n)) time on average, worst case O(n^2). * sorts the original array. */ - template + 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. diff --git a/nucleus/library/tests_algorithms/test_sorts.cpp b/nucleus/library/tests_algorithms/test_sorts.cpp index e936a721..6bc49557 100644 --- a/nucleus/library/tests_algorithms/test_sorts.cpp +++ b/nucleus/library/tests_algorithms/test_sorts.cpp @@ -47,7 +47,7 @@ public: int *populate_random_c_array(int size); basis::array populate_random_array(int size); - void rerandomize(int list[], int size); +// void rerandomize(int list[], int size); bool verify_ascending(const int *list, int size); bool verify_descending(const int *list, int size); @@ -75,11 +75,11 @@ basis::array test_sorts::populate_random_array(int size) return to_return; } -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::rerandomize(int list[], int size) +//{ +// for (int i = 0; i < size; i++) +// list[i] = randomizer().inclusive(0, MAX_VALUE); +//} bool test_sorts::verify_ascending(const int *list, int size) { @@ -114,7 +114,7 @@ void test_sorts::test_shell_sort(int size) ASSERT_TRUE(verify_ascending(list, size), "ordering check - list should be ordered at first check"); - rerandomize(list, size); + randomize_list(list, size); // check a reversed sort. shell_sort(list, size, true); @@ -136,7 +136,7 @@ void test_sorts::test_heap_sort(int size) ASSERT_TRUE(verify_ascending(list, size), "ordering check - list should be ordered at first check"); - rerandomize(list, size); + randomize_list(list, size); // check a reversed sort. heap_sort(list, size, true); @@ -161,7 +161,7 @@ void test_sorts::test_merge_sort(int size) ASSERT_TRUE(verify_ascending(ret.access(), size), "ordering check - list should be ordered at first check"); - rerandomize(list.access(), size); + randomize_list(list.access(), size); // check a reversed sort. ret = merge_sort(list, true); @@ -182,7 +182,7 @@ void test_sorts::test_quick_sort(int size) // LOG(a_sprintf("after quick sort: %s", dump_list(list, size).s())); - rerandomize(list, size); + randomize_list(list, size); // check a reversed sort. quick_sort(list, size, true); diff --git a/nucleus/library/tests_nodes/test_singly_linked_list.cpp b/nucleus/library/tests_nodes/test_singly_linked_list.cpp index e5e88c58..391cac9d 100644 --- a/nucleus/library/tests_nodes/test_singly_linked_list.cpp +++ b/nucleus/library/tests_nodes/test_singly_linked_list.cpp @@ -90,7 +90,7 @@ int test_singly_linked_list::execute() b->set_next(c); c->set_next(d); d->set_next(e); -// e->set_next(NULL_POINTER); // not actually necessary, right? + // it's not necessary to set e's next to null; this is the default. ASSERT_FALSE(singly_linked_list::has_cycle(a), "list should be found to have zero cycles") } -- 2.34.1