1 //----------------------------------------------------------------------------
2 /// @file test_insert_sort.cpp
3 /// @brief Test program of the insert_sort algorithm
4 ///
5 /// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n
6 /// Distributed under the Boost Software License, Version 1.0.\n
7 /// ( See accompanying file LICENSE_1_0.txt or copy at
8 /// http://www.boost.org/LICENSE_1_0.txt )
9 /// @version 0.1
10 ///
11 /// @remarks
12 //-----------------------------------------------------------------------------
13 #include <ciso646>
14 #include <iostream>
15 #include <stdio.h>
16 #include <stdlib.h>
17 #include <time.h>
18 #include <vector>
19 #include <boost/sort/insert_sort/insert_sort.hpp>
20 #include <boost/test/included/test_exec_monitor.hpp>
21 #include <boost/test/test_tools.hpp>
22
23
24 using namespace boost::sort;
25 using namespace std;
26 using boost::sort::common::util::insert_sorted;
27
test01(void)28 void test01 (void)
29 {
30 unsigned A[] = {7, 4, 23, 15, 17, 2, 24, 13, 8, 3, 11,
31 16, 6, 14, 21, 5, 1, 12, 19, 22, 25, 8};
32
33 std::less< unsigned > comp;
34 // Insertion Sort Unordered, not repeated
35 insert_sort (&A[ 0 ], &A[ 22 ], comp);
36 for (unsigned i = 0; i < 21; i++) {
37 BOOST_CHECK (A[ i ] <= A[ i + 1 ]);
38 };
39
40 unsigned B[] = {1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12,
41 13, 14, 15, 17, 18, 19, 20, 21, 23, 24, 25};
42 // Insertion Sort Ordered, not repeated
43 insert_sort (&B[ 0 ], &B[ 22 ], comp);
44 for (unsigned i = 0; i < 21; i++) {
45 BOOST_CHECK (B[ i ] <= B[ i + 1 ]);
46 };
47
48 unsigned C[] = {27, 26, 25, 23, 22, 21, 19, 18, 17, 16, 15,
49 14, 13, 11, 10, 9, 8, 7, 6, 5, 3, 2};
50 // Insertion Sort reverse sorted, not repeated
51 insert_sort (&C[ 0 ], &C[ 22 ], comp);
52 for (unsigned i = 0; i < 21; i++) {
53 BOOST_CHECK (C[ i ] <= C[ i + 1 ]);
54 };
55
56 unsigned D[] = {4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
57 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4};
58 // Insertion Sort equal elements
59 insert_sort (&D[ 0 ], &D[ 22 ], comp);
60 for (unsigned i = 0; i < 21; i++) {
61 BOOST_CHECK (D[ i ] <= D[ i + 1 ]);
62 };
63
64 // Insertion Sort 100 random elements
65 unsigned F[ 100 ];
66 for (unsigned i = 0; i < 100; i++) F[ i ] = rand ( ) % 1000;
67 insert_sort (&F[ 0 ], &F[ 100 ], comp);
68 for (unsigned i = 0; i < 99; i++) {
69 BOOST_CHECK (F[ i ] <= F[ i + 1 ]);
70 };
71
72 const unsigned NG = 10000;
73 // Insertion Sort "<<NG<<" random elements
74 unsigned G[ NG ];
75 for (unsigned i = 0; i < NG; i++) G[ i ] = rand ( ) % 1000;
76 insert_sort (&G[ 0 ], &G[ NG ], comp);
77 for (unsigned i = 0; i < NG - 1; i++) {
78 BOOST_CHECK (G[ i ] <= G[ i + 1 ]);
79 };
80 };
test02(void)81 void test02 (void)
82 {
83 typedef typename std::vector< uint64_t >::iterator iter_t;
84 const uint32_t NELEM = 6667;
85 std::vector< uint64_t > A;
86 std::less< uint64_t > comp;
87
88 for (uint32_t i = 0; i < 1000; ++i) A.push_back (0);
89 for (uint32_t i = 0; i < NELEM; ++i) A.push_back (NELEM - i);
90 for (uint32_t i = 0; i < 1000; ++i) A.push_back (0);
91
92 insert_sort (A.begin ( ) + 1000, A.begin ( ) + (1000 + NELEM), comp);
93
94 for (iter_t it = A.begin ( ) + 1000; it != A.begin ( ) + (1000 + NELEM);
95 ++it)
96 {
97 BOOST_CHECK ((*(it - 1)) <= (*it));
98 };
99 BOOST_CHECK (A[ 998 ] == 0 and A[ 999 ] == 0 and A[ 1000 + NELEM ] == 0 and
100 A[ 1001 + NELEM ] == 0);
101
102
103 A.clear ( );
104 for (uint32_t i = 0; i < 1000; ++i) A.push_back (999999999);
105 for (uint32_t i = 0; i < NELEM; ++i) A.push_back (NELEM - i);
106 for (uint32_t i = 0; i < 1000; ++i) A.push_back (999999999);
107
108 insert_sort (A.begin ( ) + 1000, A.begin ( ) + (1000 + NELEM), comp);
109
110 for (iter_t it = A.begin ( ) + 1001; it != A.begin ( ) + (1000 + NELEM);
111 ++it)
112 {
113 BOOST_CHECK ((*(it - 1)) <= (*it));
114 };
115 BOOST_CHECK (A[ 998 ] == 999999999 and A[ 999 ] == 999999999 and
116 A[ 1000 + NELEM ] == 999999999 and
117 A[ 1001 + NELEM ] == 999999999);
118 };
119
120
test03(void)121 void test03 ( void)
122 {
123 std::vector<uint32_t> V {1,3,5,2,4};
124 std::less<uint32_t> comp ;
125 uint32_t aux[10] ;
126
127 insert_sorted ( V.begin() , V.begin()+3, V.end(), comp, aux);
128 //insert_partial_sort ( V.begin() , V.begin()+3, V.end() , comp);
129 for ( uint32_t i =0 ; i < V.size() ; ++i)
130 std::cout<<V[i]<<", ";
131 std::cout<<std::endl;
132
133 V ={3,5,7,9,11,13,15,17,19,8,6,10,4,2};
134 insert_sorted ( V.begin() , V.begin()+9, V.end() , comp, aux);
135 //insert_partial_sort ( V.begin() , V.begin()+9, V.end() , comp);
136 for ( uint32_t i =0 ; i < V.size() ; ++i)
137 std::cout<<V[i]<<", ";
138 std::cout<<std::endl;
139
140 V ={13,15,17,19,21,23,35,27,29,8,6,10,4,2};
141 insert_sorted ( V.begin() , V.begin()+9, V.end() , comp, aux);
142 //insert_partial_sort ( V.begin() , V.begin()+9, V.end() , comp);
143 for ( uint32_t i =0 ; i < V.size() ; ++i)
144 std::cout<<V[i]<<", ";
145 std::cout<<std::endl;
146
147 V ={3,5,7,9,11,13,15,17,19,28,26,30,24,22};
148 insert_sorted ( V.begin() , V.begin()+9, V.end() , comp, aux);
149 //insert_partial_sort ( V.begin() , V.begin()+9, V.end() , comp);
150 for ( uint32_t i =0 ; i < V.size() ; ++i)
151 std::cout<<V[i]<<", ";
152 std::cout<<std::endl;
153
154
155
156 }
test_main(int,char * [])157 int test_main (int, char *[])
158 {
159 test01 ( );
160 test02 ( );
161 test03 ( );
162 return 0;
163 }
164