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 < std ::_Iter_value_t < _BidIt > > :: iterator > ,
_isort_list_tag, _isort_direct_tag > {});
}
template < typename _BidIt >
void insertionsort(_BidIt first, _BidIt last)
{
insertionsort(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;
}
using namespace std ;
using UID = uniform_int_distribution < > ;
random_device rd;
default_random_engine dre(rd()); // 난수 생성기
int main()
{
cout < < "시작하려면 아무 키나 입력
" ;
getche();
cout < < "
" ;
constexpr size_t cont_size = 100000 ;
UID uid{ 0 , cont_size - 1 };
list < int > nlist;
vector < int > narray;
auto sort_and_report_list = [ & ]( const string & assign_message)
{
cout < < "[ 삽입 정렬 ] ----------------------------------------------------
" ;
cout < < pretty_num(nlist. size ()) < < assign_message;
cout < < woon2::functimer([ & nlist]() {
woon2::insertionsort( begin (nlist), end (nlist));
}) < < "s 소요
" ;
cout < < "------------------------------------------------------------------
" ;
auto prev_end = _Prev_iter(nlist. end ());
bool is_sorted = true ;
for ( auto iter = nlist.cbegin(); iter ! = prev_end; + + iter)
if ( * iter > * _Next_iter(iter))
is_sorted = false ;
if (is_sorted)
cout < < "연속된 요소 검사, 정렬되지 않은 구간 존재하지 않았음
" ;
cout < < "원소 액세스 횟수 : " < < pretty_num(woon2::access_cnt) < < " 회" < < endl ;
cout < < "비교 연산 횟수 : " < < pretty_num(woon2::compare_cnt) < < " 회" < < endl ;
cout < < "
" ;
};
auto sort_and_report_array = [ & ]( const string & assign_message)
{
cout < < "[ 삽입 정렬 ] ----------------------------------------------------
" ;
cout < < pretty_num(narray. size ()) < < assign_message;
cout < < woon2::functimer([ & narray]() {
woon2::insertionsort( begin (narray), end (narray));
}) < < "s 소요
" ;
cout < < "------------------------------------------------------------------
" ;
auto prev_end = _Prev_iter(narray. end ());
bool is_sorted = true ;
for ( auto iter = narray.cbegin(); iter ! = prev_end; + + iter)
if ( * iter > * _Next_iter(iter))
is_sorted = false ;
if (is_sorted)
cout < < "연속된 요소 검사, 정렬되지 않은 구간 존재하지 않았음
" ;
cout < < "원소 액세스 횟수 : " < < pretty_num(woon2::access_cnt) < < " 회" < < endl ;
cout < < "비교 연산 횟수 : " < < pretty_num(woon2::compare_cnt) < < " 회" < < endl ;
cout < < "
" ;
};
// ------------------- 랜덤 데이터 ----------------------
for ( int i = 0 ; i < cont_size; + + i)
nlist. push_back (uid(dre));
// ------------------------------------------------------
sort_and_report_list( " 개의 랜덤한 정수 정렬
" );
nlist.clear();
woon2::clear_sort_report();
// --------------- 거의 정렬된 데이터 -------------------
for ( int i = 0 ; i < cont_size; + + i)
if (i % static_cast < size_t > (sqrt(cont_size)))
nlist. push_back (i);
else
nlist. push_back (uid(dre));
// ------------------------------------------------------
sort_and_report_list( " 개의 거의 정렬된 정수 정렬
" );
nlist.clear();
woon2::clear_sort_report();
// ------------------- 랜덤 데이터 ----------------------
for ( int i = 0 ; i < cont_size; + + i)
narray. push_back (uid(dre));
// ------------------------------------------------------
sort_and_report_array( " 개의 랜덤한 정수 정렬
" );
narray.clear();
woon2::clear_sort_report();
// --------------- 거의 정렬된 데이터 -------------------
for ( int i = 0 ; i < cont_size; + + i)
narray. push_back (i);
auto make_some_swaps = static_cast < size_t > (sqrt(cont_size));
for ( int i = 0 ; i < make_some_swaps; + + i)
swap(narray.at(uid(dre)), narray.at(uid(dre)));
// ------------------------------------------------------
sort_and_report_array( " 개의 거의 정렬된 정수 정렬
" );
narray.clear();
woon2::clear_sort_report();
}
from http://jartlife.tistory.com/39 by ccl(S) rewrite - 2021-08-05 21:26:35