X-Git-Url: https://feistymeow.org/gitweb/?a=blobdiff_plain;f=nucleus%2Flibrary%2Ftests_algorithms%2Ftest_sorts.cpp;h=6bc49557e619172ce2c9c1a7281e98383fee22b1;hb=bb5f4d50a726519bfd789eed499a686a29535341;hp=0edc61bb9e7a16d0ce59f389850bd124d3779504;hpb=0cc8bcdf18d075ad1297a054e571570e75624e84;p=feisty_meow.git

diff --git a/nucleus/library/tests_algorithms/test_sorts.cpp b/nucleus/library/tests_algorithms/test_sorts.cpp
index 0edc61bb..6bc49557 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<int> 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<int> &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<int> 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);
+//}
+
+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 *list, int size)
+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);
+	randomize_list(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);
+	randomize_list(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<int> &list)
+void test_sorts::test_merge_sort(int size)
 {
 	FUNCDEF("test_merge_sort");
 
+	basis::array<int> list = populate_random_array(size);
+
 	// check a normal sort.
 	basis::array<int> 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);
+	randomize_list(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()));
+
+	randomize_list(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<int> 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();
 }