123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163 |
- //----------------------------------------------------------------------------
- /// @file test_insert_sort.cpp
- /// @brief Test program of the insert_sort algorithm
- ///
- /// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n
- /// Distributed under the Boost Software License, Version 1.0.\n
- /// ( See accompanying file LICENSE_1_0.txt or copy at
- /// http://www.boost.org/LICENSE_1_0.txt )
- /// @version 0.1
- ///
- /// @remarks
- //-----------------------------------------------------------------------------
- #include <ciso646>
- #include <iostream>
- #include <stdio.h>
- #include <stdlib.h>
- #include <time.h>
- #include <vector>
- #include <boost/sort/insert_sort/insert_sort.hpp>
- #include <boost/test/included/test_exec_monitor.hpp>
- #include <boost/test/test_tools.hpp>
- using namespace boost::sort;
- using namespace std;
- using boost::sort::common::util::insert_sorted;
- void test01 (void)
- {
- unsigned A[] = {7, 4, 23, 15, 17, 2, 24, 13, 8, 3, 11,
- 16, 6, 14, 21, 5, 1, 12, 19, 22, 25, 8};
- std::less< unsigned > comp;
- // Insertion Sort Unordered, not repeated
- insert_sort (&A[ 0 ], &A[ 22 ], comp);
- for (unsigned i = 0; i < 21; i++) {
- BOOST_CHECK (A[ i ] <= A[ i + 1 ]);
- };
- unsigned B[] = {1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12,
- 13, 14, 15, 17, 18, 19, 20, 21, 23, 24, 25};
- // Insertion Sort Ordered, not repeated
- insert_sort (&B[ 0 ], &B[ 22 ], comp);
- for (unsigned i = 0; i < 21; i++) {
- BOOST_CHECK (B[ i ] <= B[ i + 1 ]);
- };
- unsigned C[] = {27, 26, 25, 23, 22, 21, 19, 18, 17, 16, 15,
- 14, 13, 11, 10, 9, 8, 7, 6, 5, 3, 2};
- // Insertion Sort reverse sorted, not repeated
- insert_sort (&C[ 0 ], &C[ 22 ], comp);
- for (unsigned i = 0; i < 21; i++) {
- BOOST_CHECK (C[ i ] <= C[ i + 1 ]);
- };
- unsigned D[] = {4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
- 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4};
- // Insertion Sort equal elements
- insert_sort (&D[ 0 ], &D[ 22 ], comp);
- for (unsigned i = 0; i < 21; i++) {
- BOOST_CHECK (D[ i ] <= D[ i + 1 ]);
- };
- // Insertion Sort 100 random elements
- unsigned F[ 100 ];
- for (unsigned i = 0; i < 100; i++) F[ i ] = rand ( ) % 1000;
- insert_sort (&F[ 0 ], &F[ 100 ], comp);
- for (unsigned i = 0; i < 99; i++) {
- BOOST_CHECK (F[ i ] <= F[ i + 1 ]);
- };
- const unsigned NG = 10000;
- // Insertion Sort "<<NG<<" random elements
- unsigned G[ NG ];
- for (unsigned i = 0; i < NG; i++) G[ i ] = rand ( ) % 1000;
- insert_sort (&G[ 0 ], &G[ NG ], comp);
- for (unsigned i = 0; i < NG - 1; i++) {
- BOOST_CHECK (G[ i ] <= G[ i + 1 ]);
- };
- };
- void test02 (void)
- {
- typedef typename std::vector< uint64_t >::iterator iter_t;
- const uint32_t NELEM = 6667;
- std::vector< uint64_t > A;
- std::less< uint64_t > comp;
- for (uint32_t i = 0; i < 1000; ++i) A.push_back (0);
- for (uint32_t i = 0; i < NELEM; ++i) A.push_back (NELEM - i);
- for (uint32_t i = 0; i < 1000; ++i) A.push_back (0);
- insert_sort (A.begin ( ) + 1000, A.begin ( ) + (1000 + NELEM), comp);
- for (iter_t it = A.begin ( ) + 1000; it != A.begin ( ) + (1000 + NELEM);
- ++it)
- {
- BOOST_CHECK ((*(it - 1)) <= (*it));
- };
- BOOST_CHECK (A[ 998 ] == 0 and A[ 999 ] == 0 and A[ 1000 + NELEM ] == 0 and
- A[ 1001 + NELEM ] == 0);
- A.clear ( );
- for (uint32_t i = 0; i < 1000; ++i) A.push_back (999999999);
- for (uint32_t i = 0; i < NELEM; ++i) A.push_back (NELEM - i);
- for (uint32_t i = 0; i < 1000; ++i) A.push_back (999999999);
- insert_sort (A.begin ( ) + 1000, A.begin ( ) + (1000 + NELEM), comp);
- for (iter_t it = A.begin ( ) + 1001; it != A.begin ( ) + (1000 + NELEM);
- ++it)
- {
- BOOST_CHECK ((*(it - 1)) <= (*it));
- };
- BOOST_CHECK (A[ 998 ] == 999999999 and A[ 999 ] == 999999999 and
- A[ 1000 + NELEM ] == 999999999 and
- A[ 1001 + NELEM ] == 999999999);
- };
- void test03 ( void)
- {
- std::vector<uint32_t> V {1,3,5,2,4};
- std::less<uint32_t> comp ;
- uint32_t aux[10] ;
- insert_sorted ( V.begin() , V.begin()+3, V.end(), comp, aux);
- //insert_partial_sort ( V.begin() , V.begin()+3, V.end() , comp);
- for ( uint32_t i =0 ; i < V.size() ; ++i)
- std::cout<<V[i]<<", ";
- std::cout<<std::endl;
- V ={3,5,7,9,11,13,15,17,19,8,6,10,4,2};
- insert_sorted ( V.begin() , V.begin()+9, V.end() , comp, aux);
- //insert_partial_sort ( V.begin() , V.begin()+9, V.end() , comp);
- for ( uint32_t i =0 ; i < V.size() ; ++i)
- std::cout<<V[i]<<", ";
- std::cout<<std::endl;
- V ={13,15,17,19,21,23,35,27,29,8,6,10,4,2};
- insert_sorted ( V.begin() , V.begin()+9, V.end() , comp, aux);
- //insert_partial_sort ( V.begin() , V.begin()+9, V.end() , comp);
- for ( uint32_t i =0 ; i < V.size() ; ++i)
- std::cout<<V[i]<<", ";
- std::cout<<std::endl;
- V ={3,5,7,9,11,13,15,17,19,28,26,30,24,22};
- insert_sorted ( V.begin() , V.begin()+9, V.end() , comp, aux);
- //insert_partial_sort ( V.begin() , V.begin()+9, V.end() , comp);
- for ( uint32_t i =0 ; i < V.size() ; ++i)
- std::cout<<V[i]<<", ";
- std::cout<<std::endl;
- }
- int test_main (int, char *[])
- {
- test01 ( );
- test02 ( );
- test03 ( );
- return 0;
- }
|