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.
+++ /dev/null
-\r
-\r
-// sole purpose of this is to make the lib be generated,\r
-// even though we currently do not have any code that lives inside it.\r
-\r
-int __private_private_bogus_placeholder_xj27_qx19() { return 32; }\r
-\r
-\r
// Please send updates for this code to: fred@gruntose.com -- Thanks, fred.
//////////////
// Please send updates for this code to: fred@gruntose.com -- Thanks, fred.
//////////////
+#include <mathematics/chaos.h>
+
namespace algorithms {
/*
namespace algorithms {
/*
* operates in O(n log(n)) time on average, worst case O(n^2).
* sorts the original array.
*/
* operates in O(n log(n)) time on average, worst case O(n^2).
* sorts the original array.
*/
void quick_sort(type v[], int n, bool reverse = false)
{
inner_quick_sort(v, 0, n - 1, reverse);
}
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 <class type>
+ 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.
} // namespace.
#endif // outer guard.
int *populate_random_c_array(int size);
basis::array<int> populate_random_array(int size);
int *populate_random_c_array(int size);
basis::array<int> 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);
bool verify_ascending(const int *list, int size);
bool verify_descending(const int *list, int size);
-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)
{
bool test_sorts::verify_ascending(const int *list, int size)
{
ASSERT_TRUE(verify_ascending(list, size),
"ordering check - list should be ordered at first check");
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);
// check a reversed sort.
shell_sort(list, size, true);
ASSERT_TRUE(verify_ascending(list, size),
"ordering check - list should be ordered at first check");
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);
// check a reversed sort.
heap_sort(list, size, true);
ASSERT_TRUE(verify_ascending(ret.access(), size),
"ordering check - list should be ordered at first check");
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);
// check a reversed sort.
ret = merge_sort(list, true);
// LOG(a_sprintf("after quick sort: %s", dump_list(list, size).s()));
// 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);
// check a reversed sort.
quick_sort(list, size, true);
b->set_next(c);
c->set_next(d);
d->set_next(e);
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")
}
ASSERT_FALSE(singly_linked_list::has_cycle(a), "list should be found to have zero cycles")
}