3 * Author : Chris Koeritz
5 * Copyright (c) 1992-$now By Author. This program is free software; you can *
6 * redistribute it and/or modify it under the terms of the GNU General Public *
7 * License as published by the Free Software Foundation; either version 2 of *
8 * the License or (at your option) any later version. This is online at: *
9 * http://www.fsf.org/copyleft/gpl.html *
10 * Please send any updates to: fred@gruntose.com *
13 #include <application/hoople_main.h>
14 #include <basis/functions.h>
15 #include <basis/guards.h>
16 #include <loggers/console_logger.h>
17 #include <mathematics/chaos.h>
18 #include <structures/static_memory_gremlin.h>
19 #include <unit_test/unit_base.h>
20 #include <algorithms/sorts.h>
22 using namespace algorithms;
23 using namespace application;
24 using namespace basis;
25 using namespace loggers;
26 using namespace mathematics;
27 using namespace structures;
28 using namespace textual;
29 using namespace timely;
30 using namespace unit_test;
32 const int MAX_ELEMENTS = 1200;
34 const int MAX_VALUE = 28000;
36 #define LOG(to_print) CLASS_EMERGENCY_LOG(program_wide_logger().get(), to_print)
38 class test_sorts : virtual public unit_base, virtual public application_shell
46 DEFINE_CLASS_NAME("test_sorts")
48 int *populate_random_c_array(int size);
49 basis::array<int> populate_random_array(int size);
50 // void rerandomize(int list[], int size);
51 bool verify_ascending(const int *list, int size);
52 bool verify_descending(const int *list, int size);
54 void test_shell_sort(int size);
55 void test_heap_sort(int size);
56 void test_merge_sort(int size);
57 void test_quick_sort(int size);
59 virtual int execute();
62 int *test_sorts::populate_random_c_array(int size)
64 int *list = new int[size];
65 for (int i = 0; i < size; i++)
66 list[i] = randomizer().inclusive(0, MAX_VALUE);
70 basis::array<int> test_sorts::populate_random_array(int size)
72 basis::array<int> to_return(size);
73 for (int i = 0; i < size; i++)
74 to_return[i] = randomizer().inclusive(0, MAX_VALUE);
78 //void test_sorts::rerandomize(int list[], int size)
80 // for (int i = 0; i < size; i++)
81 // list[i] = randomizer().inclusive(0, MAX_VALUE);
84 bool test_sorts::verify_ascending(const int *list, int size)
86 FUNCDEF("verify_ascending")
88 for (int j = 1; j < size; j++) {
89 if (list[j] < last) return false;
95 bool test_sorts::verify_descending(const int *list, int size)
97 FUNCDEF("verify_descending")
99 for (int j = 1; j < size; j++) {
100 if (list[j] > last) return false;
106 void test_sorts::test_shell_sort(int size)
108 FUNCDEF("test_shell_sort");
110 int *list = populate_random_c_array(size);
112 // check a normal sort.
113 shell_sort(list, size);
114 ASSERT_TRUE(verify_ascending(list, size),
115 "ordering check - list should be ordered at first check");
117 randomize_list(list, size);
119 // check a reversed sort.
120 shell_sort(list, size, true);
121 ASSERT_TRUE(verify_descending(list, size),
122 "ordering check - list should be ordered at second check");
128 void test_sorts::test_heap_sort(int size)
130 FUNCDEF("test_heap_sort");
132 int *list = populate_random_c_array(size);
134 // check a normal sort.
135 heap_sort(list, size);
136 ASSERT_TRUE(verify_ascending(list, size),
137 "ordering check - list should be ordered at first check");
139 randomize_list(list, size);
141 // check a reversed sort.
142 heap_sort(list, size, true);
143 ASSERT_TRUE(verify_descending(list, size),
144 "ordering check - list should be ordered at second check");
150 void test_sorts::test_merge_sort(int size)
152 FUNCDEF("test_merge_sort");
154 basis::array<int> list = populate_random_array(size);
156 // check a normal sort.
157 basis::array<int> ret = merge_sort(list);
159 // LOG(astring("list has ") + dump_list(ret.observe(), ret.length()));
161 ASSERT_TRUE(verify_ascending(ret.access(), size),
162 "ordering check - list should be ordered at first check");
164 randomize_list(list.access(), size);
166 // check a reversed sort.
167 ret = merge_sort(list, true);
168 ASSERT_TRUE(verify_descending(ret.access(), size),
169 "ordering check - list should be ordered at second check");
172 void test_sorts::test_quick_sort(int size)
174 FUNCDEF("test_quick_sort");
176 int *list = populate_random_c_array(size);
178 // check a normal sort.
179 quick_sort(list, size);
180 ASSERT_TRUE(verify_ascending(list, size),
181 "ordering check - list should be ordered at first check");
183 // LOG(a_sprintf("after quick sort: %s", dump_list(list, size).s()));
185 randomize_list(list, size);
187 // check a reversed sort.
188 quick_sort(list, size, true);
189 ASSERT_TRUE(verify_descending(list, size),
190 "ordering check - list should be ordered at second check");
197 int test_sorts::execute()
201 int size = MAX_ELEMENTS;
203 test_shell_sort(size);
205 test_heap_sort(size);
207 test_merge_sort(size);
209 test_quick_sort(size);
211 return final_report();
214 HOOPLE_MAIN(test_sorts,)