on
이진 삽입 정렬 - STL 호환
이진 삽입 정렬 - STL 호환
#include < iostream >
#include < random >
#include < vector >
#include < list >
#include < string >
#include < conio.h >
#include < chrono >
#include < cmath >
#define _woon2sort_enable_investigation
namespace woon2
{
using nanoseconds = std ::chrono::nanoseconds;
using microseconds = std ::chrono::microseconds;
using milliseconds = std ::chrono::milliseconds;
using seconds = std ::chrono::seconds;
// 함수를 받아 실행하고 실행 시간을 반환하는 함수
template < typename _Tt = seconds, typename _F > // 기본 반환 단위 : seconds
auto functimer(_F func)
{
using namespace std ::chrono;
using CountType = nanoseconds; // ns 단위로 세고
using TimeType = _Tt; // 전해진 단위로 반환
auto tp = system_clock::now();
func();
auto passed = duration_cast < CountType > (system_clock::now() - tp).count();
return passed / static_cast < long double > (CountType::period::den / TimeType::period::den);
}
#ifdef _woon2sort_enable_investigation
unsigned long long access_cnt{ 0 };
unsigned long long compare_cnt{ 0 };
void clear_sort_report()
{
access_cnt = 0 ;
compare_cnt = 0 ;
}
void _access(size_t cnt)
{
access_cnt + = cnt;
}
void _compare(size_t cnt)
{
compare_cnt + = cnt;
}
#endif
struct _isort_direct_tag {};
struct _isort_list_tag {};
template < typename _BidIt, typename _Pr >
void _insertionsort(_BidIt first, _BidIt last, _Pr pred, _isort_direct_tag)
{
std :: cout < < "다이렉트 버전 호출
" ;
// [first, last) order
for ( auto item = std ::_Next_iter(first); item ! = last; + + item)
{
#ifdef _woon2sort_enable_investigation
_access( 4 );
_compare( 1 );
#endif
auto key = * item;
auto before_fit = item;
while ( - - before_fit ! = first & & pred(key, * before_fit))
{
#ifdef _woon2sort_enable_investigation
_access( 4 );
_compare( 1 );
#endif
* ( std ::_Next_iter(before_fit)) = std ::move( * before_fit);
}
if (pred(key, * first))
{
#ifdef _woon2sort_enable_investigation
_access( 6 );
_compare( 1 );
#endif
* ( std ::_Next_iter(first)) = std ::move( * first);
* first = std ::move(key);
}
else
{
#ifdef _woon2sort_enable_investigation
_access( 4 );
_compare( 1 );
#endif
* ( + + before_fit) = std ::move(key);
}
}
}
template < typename _ListIt >
void _move_node_from_to(_ListIt from, _ListIt to)
{
// from being next of to
from._Ptr - > _Next - > _Prev = from._Ptr - > _Prev;
from._Ptr - > _Prev - > _Next = from._Ptr - > _Next; // extract
from._Ptr - > _Next = to._Ptr - > _Next; // insert
from._Ptr - > _Prev = to._Ptr;
to._Ptr - > _Next - > _Prev = from._Ptr;
to._Ptr - > _Next = from._Ptr;
}
template < typename _BidIt, typename _Pr >
void _insertionsort(_BidIt first, _BidIt last, _Pr pred, _isort_list_tag)
{
std :: cout < < "리스트 버전 호출
" ;
// [first, last) order
for (decltype(first) item = std ::_Next_iter(first), next_item; item ! = last; item = next_item)
{
next_item = std ::_Next_iter(item);
auto before_fit = item;
if (pred( * item, * first))
{
#ifdef _woon2sort_enable_investigation
_access( 8 );
_compare( 1 );
#endif
std ::swap( * item, * first); // first should remain head of list
_move_node_from_to(item, first);
}
else
{
#ifdef _woon2sort_enable_investigation
_access( 2 );
_compare( 1 );
#endif
while ( - - before_fit ! = first & & pred( * item, * before_fit))
{
#ifdef _woon2sort_enable_investigation
_access( 2 );
_compare( 1 );
#endif
}
_move_node_from_to(item, before_fit);
}
}
}
template < typename _BidIt, typename _Pr >
void insertionsort(_BidIt first, _BidIt last, _Pr pred)
{
_insertionsort(first, last, pred,
std ::conditional_t < std ::is_same_v < _BidIt, typename std ::list < _BidIt::value_type > :: iterator > ,
_isort_list_tag, _isort_direct_tag > {});
}
template < typename _BidIt >
void insertionsort(_BidIt first, _BidIt last)
{
insertionsort(first, last, std ::less < > {});
}
struct _isort_bin_ranit_tag {};
struct _isort_bin_fwdit_tag {};
constexpr size_t _isort_bin_entry_size = 16 ;
template < typename _RanIt, typename _Pr >
void _insertionsort_bin(_RanIt first, _RanIt last, _Pr pred, _isort_bin_ranit_tag)
{
std :: cout < < "임의 접근 반복자 버전 호출
" ;
// [first, last) order
for ( auto item = first + 1 ; item < last; + + item)
{
auto key = * item;
auto left = first;
auto right = item;
while (left < right)
{
#ifdef _woon2sort_enable_investigation
_access( 2 );
_compare( 1 );
#endif
auto mid = left + ((right - left) > > 1 );
if (pred(key, * mid))
right = mid;
else
left = mid + 1 ;
}
#ifdef _woon2sort_enable_investigation
_access( 4 + (item - left) * 2 );
#endif
std ::move(left, item, left + 1 );
* left = std ::move(key);
}
}
template < typename _FwdIt >
auto _distance_fwdit(_FwdIt first, _FwdIt last)
{
std ::_Iter_diff_t < decltype(first) > diff = 0 ;
for ( auto iter = first; iter ! = last; + + iter)
+ + diff;
return diff;
}
template < typename _FwdIt, typename _Pr >
void _insertionsort_bin(_FwdIt first, _FwdIt last, _Pr pred, _isort_bin_fwdit_tag)
{
std :: cout < < "순방향 반복자 버전 호출
" ;
// [first, last) order
for ( auto item = std ::_Next_iter(first); item ! = last; + + item)
{
auto key = * item;
auto left = first;
auto right = item;
while (left ! = right)
{
auto mid = left;
auto half_diff = _distance_fwdit(left, right) / 2 ;
for (decltype(half_diff) i = 0 ; i < half_diff; + + i)
+ + mid;
#ifdef _woon2sort_enable_investigation
_access( 2 );
_compare( 1 );
#endif
if (pred(key, * mid))
right = mid;
else
left = + + mid;
}
#ifdef _woon2sort_enable_investigation
_access( 4 + _distance_fwdit(left, item) * 2 );
#endif
std ::move(left, item, std ::_Next_iter(left));
* left = std ::move(key);
}
}
template < typename _BidIt, typename _Pr >
void insertionsort_bin(_BidIt first, _BidIt last, _Pr pred)
{
_insertionsort_bin(first, last, pred, std ::conditional_t < std ::_Is_random_iter_v < decltype(first) > ,
_isort_bin_ranit_tag, _isort_bin_fwdit_tag > {});
}
template < typename _BidIt >
void insertionsort_bin(_BidIt first, _BidIt last)
{
insertionsort_bin(first, last, std ::less < > {});
}
}
template < typename _Nt >
auto pretty_num(_Nt n)
{
auto str = std ::move( std ::to_string(n));
for ( int i = str.length(), cnt = 0 ; i > 0 ; - - i, + + cnt)
if (cnt & & ! (cnt % 3 ))
str.insert(i, "\'" );
return str;
}
template < typename _Cont, typename _SortFunc >
void sort_then_report(_Cont & & container, const std :: string & sort_name, _SortFunc sort, const std :: string & how_elems_generated)
{
std :: cout < < "[ " < < sort_name < < " ] ----------------------------------------------------
" ;
std :: cout < < pretty_num(container. size ()) < < how_elems_generated < < std :: endl ;
std :: cout < < woon2::functimer([ & container, & sort]() {
sort( begin (container), end (container));
}) < < "s 소요
" ;
std :: cout < < "------------------------------------------------------------------
" ;
auto prev_end = _Prev_iter(cend(container));
bool is_sorted = true ;
for ( auto iter = cbegin(container); iter ! = prev_end; + + iter)
if ( * iter > * _Next_iter(iter))
is_sorted = false ;
if (is_sorted)
std :: cout < < "연속된 요소 검사, 정렬되지 않은 구간 존재하지 않았음
" ;
std :: cout < < "원소 액세스 횟수 : " < < pretty_num(woon2::access_cnt) < < " 회" < < std :: endl ;
std :: cout < < "비교 연산 횟수 : " < < pretty_num(woon2::compare_cnt) < < " 회" < < std :: endl ;
std :: cout < < "
" ;
woon2::clear_sort_report();
}
using UID = std ::uniform_int_distribution < > ;
std ::random_device rd;
std ::default_random_engine dre(rd()); // 난수 생성기
template < typename _Cont >
void create_random_data(_Cont & & container, const int data_size)
{
UID uid{ 0 , data_size - 1 };
for ( int i = 0 ; i < data_size; + + i)
container. push_back (uid(dre));
}
template < typename _Cont >
void create_almost_sorted_data(_Cont & & container, const int data_size)
{
UID uid{ 0 , data_size - 1 };
for ( int i = 0 ; i < data_size; + + i)
if (i % static_cast < size_t > (sqrt(data_size) / 2 ))
container. push_back (i);
else
container. push_back (uid(dre));
}
int main()
{
using namespace std ;
cout < < "시작하려면 아무 키나 입력
" ;
getche();
cout < < "
" ;
vector < int > narray;
constexpr size_t cont_size = 1 '000' 000 ;
narray.reserve(cont_size);
const string sort_name = "삽입 정렬" ;
const string sort_name_bin = "이진 삽입 정렬" ;
const string random_assigned = " 개의 랜덤한 정수 정렬" ;
const string almost_sorted_assigned = " 개의 거의 정렬된 정수 정렬" ;
auto sort_func{ woon2::insertionsort < decltype(narray):: iterator > };
auto sort_func_bin{ woon2::insertionsort_bin < decltype(narray):: iterator > };
create_random_data(narray, cont_size);
sort_then_report(narray, sort_name_bin, sort_func_bin, random_assigned);
narray.clear();
create_random_data(narray, cont_size);
sort_then_report(narray, sort_name, sort_func, random_assigned);
narray.clear();
create_almost_sorted_data(narray, cont_size);
sort_then_report(narray, sort_name_bin, sort_func_bin, almost_sorted_assigned);
narray.clear();
create_almost_sorted_data(narray, cont_size);
sort_then_report(narray, sort_name, sort_func, almost_sorted_assigned);
narray.clear();
}
from http://jartlife.tistory.com/41 by ccl(S) rewrite - 2021-08-08 05:00:44