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
24using namespace boost::sort;
25using namespace std;
26
27void test01 (void)
28{
29 unsigned A[] = {7, 4, 23, 15, 17, 2, 24, 13, 8, 3, 11,
30 16, 6, 14, 21, 5, 1, 12, 19, 22, 25, 8};
31
32 std::less< unsigned > comp;
33
34 // Insertion Sort sort an empty range
35 insert_sort (first: &A[ 0 ], last: &A[ 0 ], comp);
36
37 // Insertion Sort Unordered, not repeated
38 insert_sort (first: &A[ 0 ], last: &A[ 22 ], comp);
39 for (unsigned i = 0; i < 21; i++) {
40 BOOST_CHECK (A[ i ] <= A[ i + 1 ]);
41 };
42
43 unsigned B[] = {1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12,
44 13, 14, 15, 17, 18, 19, 20, 21, 23, 24, 25};
45 // Insertion Sort Ordered, not repeated
46 insert_sort (first: &B[ 0 ], last: &B[ 22 ], comp);
47 for (unsigned i = 0; i < 21; i++) {
48 BOOST_CHECK (B[ i ] <= B[ i + 1 ]);
49 };
50
51 unsigned C[] = {27, 26, 25, 23, 22, 21, 19, 18, 17, 16, 15,
52 14, 13, 11, 10, 9, 8, 7, 6, 5, 3, 2};
53 // Insertion Sort reverse sorted, not repeated
54 insert_sort (first: &C[ 0 ], last: &C[ 22 ], comp);
55 for (unsigned i = 0; i < 21; i++) {
56 BOOST_CHECK (C[ i ] <= C[ i + 1 ]);
57 };
58
59 unsigned D[] = {4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
60 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4};
61 // Insertion Sort equal elements
62 insert_sort (first: &D[ 0 ], last: &D[ 22 ], comp);
63 for (unsigned i = 0; i < 21; i++) {
64 BOOST_CHECK (D[ i ] <= D[ i + 1 ]);
65 };
66
67 // Insertion Sort 100 random elements
68 unsigned F[ 100 ];
69 for (unsigned i = 0; i < 100; i++) F[ i ] = rand ( ) % 1000;
70 insert_sort (first: &F[ 0 ], last: &F[ 100 ], comp);
71 for (unsigned i = 0; i < 99; i++) {
72 BOOST_CHECK (F[ i ] <= F[ i + 1 ]);
73 };
74
75 const unsigned NG = 10000;
76 // Insertion Sort "<<NG<<" random elements
77 unsigned G[ NG ];
78 for (unsigned i = 0; i < NG; i++) G[ i ] = rand ( ) % 1000;
79 insert_sort (first: &G[ 0 ], last: &G[ NG ], comp);
80 for (unsigned i = 0; i < NG - 1; i++) {
81 BOOST_CHECK (G[ i ] <= G[ i + 1 ]);
82 };
83};
84void test02 (void)
85{
86 typedef typename std::vector< uint64_t >::iterator iter_t;
87 const uint32_t NELEM = 6667;
88 std::vector< uint64_t > A;
89 std::less< uint64_t > comp;
90
91 for (uint32_t i = 0; i < 1000; ++i) A.push_back (x: 0);
92 for (uint32_t i = 0; i < NELEM; ++i) A.push_back (x: NELEM - i);
93 for (uint32_t i = 0; i < 1000; ++i) A.push_back (x: 0);
94
95 insert_sort (first: A.begin ( ) + 1000, last: A.begin ( ) + (1000 + NELEM), comp);
96
97 for (iter_t it = A.begin ( ) + 1000; it != A.begin ( ) + (1000 + NELEM);
98 ++it)
99 {
100 BOOST_CHECK ((*(it - 1)) <= (*it));
101 };
102 BOOST_CHECK (A[ 998 ] == 0 and A[ 999 ] == 0 and A[ 1000 + NELEM ] == 0 and
103 A[ 1001 + NELEM ] == 0);
104
105
106 A.clear ( );
107 for (uint32_t i = 0; i < 1000; ++i) A.push_back (x: 999999999);
108 for (uint32_t i = 0; i < NELEM; ++i) A.push_back (x: NELEM - i);
109 for (uint32_t i = 0; i < 1000; ++i) A.push_back (x: 999999999);
110
111 insert_sort (first: A.begin ( ) + 1000, last: A.begin ( ) + (1000 + NELEM), comp);
112
113 for (iter_t it = A.begin ( ) + 1001; it != A.begin ( ) + (1000 + NELEM);
114 ++it)
115 {
116 BOOST_CHECK ((*(it - 1)) <= (*it));
117 };
118 BOOST_CHECK (A[ 998 ] == 999999999 and A[ 999 ] == 999999999 and
119 A[ 1000 + NELEM ] == 999999999 and
120 A[ 1001 + NELEM ] == 999999999);
121};
122
123int test_main (int, char *[])
124{
125 test01 ( );
126 test02 ( );
127 return 0;
128}
129

source code of boost/libs/sort/test/test_insert_sort.cpp