introsort 링크 & 고민

https://en.wikipedia.org/wiki/Introsort

 

Quicksort 로 시작해서 원소들의 길이의 로그값을 기준으로 잡아 기준값에 도달하면 Heapsort 로 전환하고

정렬할 원소들의 수가 어떠한 임계값보다 적을 경우 Insertsort 로 전환한다.

 

GNU Standard C++ Library 의 경우, Heapsort 로 전환할 기준값을 2*Log(n) 로 두고

임계값이 16개 이하가 되면 Insertsort 로 전환한다.

(라고 적혀있어서 소스를 살펴보았다)

 

https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.4/a01347.html#l05207

 

에서 sort 소스를 따라가면 아래와 같이 찾아볼 수 있는데

05205   template<typename _RandomAccessIterator>
05206     inline void
05207     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
05208     {
05209       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05210     _ValueType;
05211 
05212       // concept requirements
05213       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05214         _RandomAccessIterator>)
05215       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
05216       __glibcxx_requires_valid_range(__first, __last);
05217 
05218       if (__first != __last)
05219     {
05220       std::__introsort_loop(__first, __last,
05221                 std::__lg(__last - __first) * 2);
05222       std::__final_insertion_sort(__first, __last);
05223     }
05224     }
05225 

std::__introsort_loop 을 따라가면

02243   template<typename _RandomAccessIterator, typename _Size>
02244     void
02245     __introsort_loop(_RandomAccessIterator __first,
02246              _RandomAccessIterator __last,
02247              _Size __depth_limit)
02248     {
02249       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02250     _ValueType;
02251 
02252       while (__last - __first > int(_S_threshold))
02253     {
02254       if (__depth_limit == 0)
02255         {
02256           _GLIBCXX_STD_P::partial_sort(__first, __last, __last);
02257           return;
02258         }
02259       --__depth_limit;
02260       _RandomAccessIterator __cut =
02261         std::__unguarded_partition(__first, __last,
02262                        _ValueType(std::__median(*__first,
02263                                 *(__first
02264                                   + (__last
02265                                      - __first)
02266                                   / 2),
02267                                 *(__last
02268                                   - 1))));
02269       std::__introsort_loop(__cut, __last, __depth_limit);
02270       __last = __cut;
02271     }
02272     }

위와 같이 나오는데, partial_sort 를 따라가면 기준값이 0이 됐을 경우라 Heapsort 가 진행되고

 

다시, sort() → std::__final_insertion_sort 를 따라가면

02168   enum { _S_threshold = 16 };
02169 
02170   /// This is a helper function for the sort routine.
02171   template<typename _RandomAccessIterator>
02172     void
02173     __final_insertion_sort(_RandomAccessIterator __first,
02174                _RandomAccessIterator __last)
02175     {
02176       if (__last - __first > int(_S_threshold))
02177     {
02178       std::__insertion_sort(__first, __first + int(_S_threshold));
02179       std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
02180     }
02181       else
02182     std::__insertion_sort(__first, __last);
02183     }

위와 같은 소스를 볼 수 있다.

 

 enum { _S_threshold = 16 };



// __introsort_loop

02252       while (__last - __first > int(_S_threshold))
02253     {
02254       if (__depth_limit == 0)
02255         {
02256           _GLIBCXX_STD_P::partial_sort(__first, __last, __last);
02257           return;
02258         }



// __final_insertion_sort

02176       if (__last - __first > int(_S_threshold))
02177     {
02178       std::__insertion_sort(__first, __first + int(_S_threshold));
02179       std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
02180     }
02181       else
02182     std::__insertion_sort(__first, __last);
02183     }

 

위 부분이 임계값에 도달했을 때의 부분인데....

 

__introsort_loop 에서 __depth_limit 이 0이 되도 함수에서 빠져나오는 것으로 보아

 

반드시 임계값이 됐을 때 루프에서 빠져나오리라는 보장은 없어보인다.

 

이를 염두해서인지 모르겠는데 __final_insertion_sort 함수에 if (__last - __first > int(_S_threshold)) ~ else 구절에서

 

무조건 삽입정렬을 하는데............................

 

음............ 나중에 구현할 일이 생기면 더 고민해봐야할거 같다.

 

일단, 깊이값을 log(원소 수)*2 으로 두고 quicksort 마냥 깊이 값까지 파티션을 나눠서 힙 정렬

힙정렬이 끝나면 삽입 정렬 정도의 개념으로 기억해둬야겠다.