extl/algorithm/test/sort_test.h

   1 /* ///////////////////////////////////////////////////////////////////////
   2  * File:                sort_test.h
   3  *
   4  * Created:             08.02.25
   5  * Updated:             08.04.15
   6  *
   7  * Brief:               The Sort Algorithm Unit-testing
   8  *
   9  * [<Home>]
  10  * Copyright (c) 2008-2020, Waruqi All rights reserved.
  11  * //////////////////////////////////////////////////////////////////// */
  12
  13 #ifndef EXTL_ALGORITHM_SORT_TEST_H
  14 #define EXTL_ALGORITHM_SORT_TEST_H
  15
  16 /* ///////////////////////////////////////////////////////////////////////
  17  * Includes
  18  */
  19 #include "../../utility/element_num.h"
  20 #include "../../functional/functional.h"
  21 #include "../../memory/buffer.h"
  22 #include "../../counter/counter.h"
  23 #include "../../math/math.h"
  24
  25 /* ///////////////////////////////////////////////////////////////////////
  26  * unit_test namespace
  27  */
  28 EXTL_BEGIN_NAMESPACE
  29 EXTL_TEST_NAME_BEGIN_NAMESPACE(sort_test)
  30
  31 struct sort_test
  32 {
  33         typedef buffer_selector<int>::buffer_type       buffer_type;
  34         void rand_make(linear_rand& r, buffer_type& buf)
  35         {
  36                 r.reset();
  37                 for (buffer_type::iterator p = buf.begin(); p != buf.end(); ++p)
  38                 {
  39                         *p = r.generate(0, 100);
  40                 }
  41         }
  42
  43         void bubble_sort_test(clock_counter& t, linear_rand& r, buffer_type& buf)
  44         {
  45                 e_size_t n = 10;
  46                 if (buf.size() <= 64) n = 100000;
  47                 if (buf.size() <= 512) n = 10000;
  48                 if (buf.size() <= 2048) n = 500;
  49                 if (buf.size() <= 4096) n = 20;
  50
  51                 rand_make(r, buf);
  52                 t.begin();
  53                 for (e_size_t i = 0; i < n; ++i)
  54                         bubble_sort(buf.begin(), buf.end());
  55                 t.end();
  56                 EXTL_TEST_TRACE(_T("bubble_sort(%d) time: %f ms"), buf.size(), e_float_t(t.ms()) / n);
  57         }
  58
  59         void insertion_sort_test(clock_counter& t, linear_rand& r, buffer_type& buf)
  60         {
  61                 e_size_t n = 10;
  62                 if (buf.size() <= 64) n = 100000;
  63                 if (buf.size() <= 512) n = 10000;
  64                 if (buf.size() <= 2048) n = 500;
  65                 if (buf.size() <= 4096) n = 20;
  66
  67                 rand_make(r, buf);
  68                 t.begin();
  69                 for (e_size_t i = 0; i < n; ++i)
  70                         insertion_sort(buf.begin(), buf.end());
  71                 t.end();
  72                 EXTL_TEST_TRACE(_T("insertion_sort(%d) time: %f ms"), buf.size(), e_float_t(t.ms()) / n);
  73         }
  74
  75         void heap_sort_test(clock_counter& t, linear_rand& r, buffer_type& buf)
  76         {
  77                 e_size_t n = 10;
  78                 if (buf.size() <= 64) n = 100000;
  79                 if (buf.size() <= 512) n = 10000;
  80                 if (buf.size() <= 2048) n = 500;
  81                 if (buf.size() <= 4096) n = 20;
  82
  83                 rand_make(r, buf);
  84                 t.begin();
  85                 for (e_size_t i = 0; i < n; ++i)
  86                         heap_sort(buf.begin(), buf.end());
  87                 t.end();
  88                 EXTL_TEST_TRACE(_T("heap_sort(%d) time: %f ms"), buf.size(), e_float_t(t.ms()) / n);
  89         }
  90
  91         sort_test()
  92         {
  93                 EXTL_TEST_TRACE(_T("sort test:"));
  94                 EXTL_TEST_TRACE(_T("///////////////////////////////////////////////////////////////////////"));
  95
  96         #ifdef EXTL_ITERATOR_POINTER_AS_ITERATOR_SUPPORT
  97                 EXTL_TEST_TRACE(_T("sort:\t\t\t568197555645645623687106443210"));
  98
  99                 #define EXTL_SORT_TEST_STR      _T("568197555645645623687106443210")
 100
 101                 // in ascending order
 102                 e_tchar_t bubble_s1[] = EXTL_SORT_TEST_STR;
 103                 e_size_t top_n = 5;
 104                 bubble_sort(bubble_s1, bubble_s1 + EXTL_ELEMENT_NUM(bubble_s1) - 1);
 105                 EXTL_TEST_TRACE(_T("bubble_sort:\t\t%s"), bubble_s1);
 106
 107                 e_tchar_t insertion_s1[] = EXTL_SORT_TEST_STR;
 108                 insertion_sort(insertion_s1, insertion_s1 + EXTL_ELEMENT_NUM(insertion_s1) - 1);
 109                 EXTL_TEST_TRACE(_T("insertion_sort:\t\t%s"), insertion_s1);
 110
 111                 e_tchar_t heap_s1[] = EXTL_SORT_TEST_STR;
 112                 heap_sort(heap_s1, heap_s1 + EXTL_ELEMENT_NUM(heap_s1) - 1);
 113                 EXTL_TEST_TRACE(_T("heap_sort:\t\t%s"), heap_s1);
 114
 115                 e_tchar_t heap_s2[] = EXTL_SORT_TEST_STR;
 116                 heap_sort_top_n(heap_s2, heap_s2 + EXTL_ELEMENT_NUM(heap_s2) - 1, top_n, std_greater<e_tchar_t>());
 117                 EXTL_TEST_TRACE(_T("heap_sort_top_n(%d):\t%s"), top_n, heap_s2);
 118
 119                 // in descending order
 120                 e_tchar_t bubble_s2[] = EXTL_SORT_TEST_STR;
 121                 bubble_sort(bubble_s2, bubble_s2 + EXTL_ELEMENT_NUM(bubble_s2) - 1, std_greater<e_tchar_t>());
 122                 EXTL_TEST_TRACE(_T("\nbubble_sort:\t\t%s"), bubble_s2);
 123
 124                 e_tchar_t insertion_s2[] = EXTL_SORT_TEST_STR;
 125                 insertion_sort(insertion_s2, insertion_s2 + EXTL_ELEMENT_NUM(insertion_s2) - 1, std_greater<e_tchar_t>());
 126                 EXTL_TEST_TRACE(_T("insertion_sort:\t\t%s"), insertion_s2);
 127
 128                 e_tchar_t heap_s3[] = EXTL_SORT_TEST_STR;
 129                 heap_sort(heap_s3, heap_s3 + EXTL_ELEMENT_NUM(heap_s3) - 1, std_greater<e_tchar_t>());
 130                 EXTL_TEST_TRACE(_T("heap_sort:\t\t%s"), heap_s3);
 131
 132                 e_tchar_t heap_s4[] = EXTL_SORT_TEST_STR;
 133                 heap_sort_top_n(heap_s4, heap_s4 + EXTL_ELEMENT_NUM(heap_s4) - 1, top_n);
 134                 EXTL_TEST_TRACE(_T("heap_sort_top_n(%d):\t%s"), top_n, heap_s4);
 135
 136
 137         #endif
 138
 139                 // performance test
 140         #ifndef EXTL_DEBUG
 141                 clock_counter t;
 142                 linear_rand     r;
 143
 144                 buffer_type     buf32(32);
 145                 buffer_type     buf64(64);
 146                 buffer_type     buf128(128);
 147                 buffer_type     buf512(512);
 148                 buffer_type     buf1024(1024);
 149                 buffer_type     buf2048(2048);
 150                 buffer_type     buf4096(4096);
 151                 buffer_type     buf8192(8192);
 152                 buffer_type     buf16384(16384);
 153                 buffer_type     buf32768(32768);
 154
 155
 156                 EXTL_TEST_TRACE(_T("\nheap_sort performance test:"));
 157                 heap_sort_test(t, r, buf32);
 158                 heap_sort_test(t, r, buf64);
 159                 heap_sort_test(t, r, buf128);
 160                 heap_sort_test(t, r, buf512);
 161                 heap_sort_test(t, r, buf1024);
 162                 heap_sort_test(t, r, buf2048);
 163                 heap_sort_test(t, r, buf4096);
 164                 heap_sort_test(t, r, buf8192);
 165                 heap_sort_test(t, r, buf16384);
 166                 heap_sort_test(t, r, buf32768);
 167
 168                 EXTL_TEST_TRACE(_T("\nbubble_sort performance test:"));
 169                 bubble_sort_test(t, r, buf32);
 170                 bubble_sort_test(t, r, buf64);
 171                 bubble_sort_test(t, r, buf128);
 172                 bubble_sort_test(t, r, buf512);
 173                 bubble_sort_test(t, r, buf1024);
 174                 bubble_sort_test(t, r, buf2048);
 175
 176                 EXTL_TEST_TRACE(_T("\ninsertion_sort performance test:"));
 177                 insertion_sort_test(t, r, buf32);
 178                 insertion_sort_test(t, r, buf64);
 179                 insertion_sort_test(t, r, buf128);
 180                 insertion_sort_test(t, r, buf512);
 181                 insertion_sort_test(t, r, buf1024);
 182                 insertion_sort_test(t, r, buf2048);
 183         #endif
 184         }
 185 };
 186
 187 sort_test g_sort_test;
 188
 189 /* ///////////////////////////////////////////////////////////////////////
 190  * unit_test namespace
 191  */
 192 EXTL_TEST_NAME_END_NAMESPACE(sort_test)
 193 EXTL_END_NAMESPACE
 194 /* //////////////////////////////////////////////////////////////////// */
 195 #endif /* EXTL_ALGORITHM_SORT_TEST_H */
 196 /* //////////////////////////////////////////////////////////////////// */