X-Git-Url: https://feistymeow.org/gitweb/?a=blobdiff_plain;f=nucleus%2Flibrary%2Ftests_algorithms%2Ftest_sorts.cpp;fp=nucleus%2Flibrary%2Ftests_algorithms%2Ftest_sorts.cpp;h=6bc49557e619172ce2c9c1a7281e98383fee22b1;hb=7b39f7e279005c8466ef508220a532ce2aa4abf8;hp=fefcb2e5fb1b330300fd104d106da9e0facb61ea;hpb=3fbd372b35b15a19fb171d5ae34294ff7b1e6485;p=feisty_meow.git

diff --git a/nucleus/library/tests_algorithms/test_sorts.cpp b/nucleus/library/tests_algorithms/test_sorts.cpp
index fefcb2e5..6bc49557 100644
--- a/nucleus/library/tests_algorithms/test_sorts.cpp
+++ b/nucleus/library/tests_algorithms/test_sorts.cpp
@@ -1,16 +1,15 @@
 /*
-*  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 <algorithms/shell_sort.h>
+ *  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 <application/hoople_main.h>
 #include <basis/functions.h>
 #include <basis/guards.h>
@@ -18,6 +17,7 @@
 #include <mathematics/chaos.h>
 #include <structures/static_memory_gremlin.h>
 #include <unit_test/unit_base.h>
+#include <algorithms/sorts.h>
 
 using namespace algorithms;
 using namespace application;
@@ -38,49 +38,178 @@ 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");
-  virtual int execute();
+	test_sorts()
+			: 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 size);
+	void test_heap_sort(int size);
+	void test_merge_sort(int size);
+	void test_quick_sort(int size);
+
+	virtual int execute();
 };
 
+int *test_sorts::populate_random_c_array(int size)
+{
+	int *list = new int[size];
+	for (int i = 0; i < size; i++)
+		list[i] = randomizer().inclusive(0, MAX_VALUE);
+	return list;
+}
+
+basis::array<int> test_sorts::populate_random_array(int size)
+{
+	basis::array<int> to_return(size);
+	for (int i = 0; i < size; i++)
+		to_return[i] = randomizer().inclusive(0, MAX_VALUE);
+	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);
+//}
+
+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);
+	ASSERT_TRUE(verify_ascending(list, size),
+	    "ordering check - list should be ordered at first check");
+
+	randomize_list(list, size);
+
+	// check a reversed sort.
+	shell_sort(list, size, true);
+	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 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");
+
+	randomize_list(list, size);
+
+	// check a reversed sort.
+	heap_sort(list, size, true);
+	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(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(astring("list has ") + dump_list(ret.observe(), ret.length()));
+
+	ASSERT_TRUE(verify_ascending(ret.access(), size),
+	    "ordering check - list should be ordered at first check");
+
+	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");
+}
+
+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 *list = new int[MAX_ELEMENTS];
-  for (int i = 0; i < MAX_ELEMENTS; i++)
-    list[i] = randomizer().inclusive(0, MAX_VALUE);
-
-//astring ret;
-//for (int i = 0; i < MAX_ELEMENTS; i++) ret += a_sprintf("%d ", list[i]);
-//LOG(ret);
-//LOG("-------------");
-
-  // check a normal sort.
-  shell_sort(list, MAX_ELEMENTS);
-  int last = -1;
-  for (int j = 0; j < MAX_ELEMENTS; 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 < MAX_ELEMENTS; i++)
-    list[i] = randomizer().inclusive(0, MAX_VALUE);
-
-  // check a reversed sort.
-  shell_sort(list, MAX_ELEMENTS, true);
-  last = MAX_VALUE + 100;  // past the maximum we'll include in the list.
-  for (int j = 0; j < MAX_ELEMENTS; j++) {
-    ASSERT_FALSE(list[j] > last, "ordering check - list should be ordered at second check");
-    last = list[j];
-  }
-
-  // clean up now.
-  delete [] list;
-
-  return final_report();
+	FUNCDEF("execute");
+
+	int size = MAX_ELEMENTS;
+
+	test_shell_sort(size);
+
+	test_heap_sort(size);
+
+	test_merge_sort(size);
+
+	test_quick_sort(size);
+
+	return final_report();
 }
 
-HOOPLE_MAIN(test_sorts, )
+HOOPLE_MAIN(test_sorts,)