std::sort()

오늘 면접 진행하면서 C++ 및 컴퓨터 이론 기초에서 터지는 사고가 좀 발생했는데(...)

 

그중에 정렬문제가 있었다.

 

문제 자체는 퀵소트 관련 질문이었는데, 문득 "언리얼에서는 기본 정렬로직을 뭘 쓰더라?" 하고 찾아보니, C++ standard에 포함된 std::sort()를 사용한다고 되어있었다.

 

거기는 또 뭘 쓰냐 봤더니... 퀵 정렬이 아닌 "Intro Sort" 라는 개선형 퀵 정렬을 사용하고 있었다.

 

 

---

해당 자료는 온라인 코드 브라우저의 gcc 컴파일러 기준 C++ 11 로직을 참고하였습니다. : https://codebrowser.dev/gcc/include/c++/11/bits/stl_algo.h.htm

---

우선, std::sort를 검색하면 std::__sort 라는 inner func가 나온다.

 

  /**
   *  @brief Sort the elements of a sequence using a predicate for comparison.
   *  @ingroup sorting_algorithms
   *  @param  __first   An iterator.
   *  @param  __last    Another iterator.
   *  @param  __comp    A comparison functor.
   *  @return  Nothing.
   *
   *  Sorts the elements in the range @p [__first,__last) in ascending order,
   *  such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
   *  range @p [__first,__last-1).
   *
   *  The relative ordering of equivalent elements is not preserved, use
   *  @p stable_sort() if this is needed.
  */
  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    inline void
    sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
         _Compare __comp)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
      __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
            typename iterator_traits<_RandomAccessIterator>::value_type,
            typename iterator_traits<_RandomAccessIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __last);
      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
      std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
    }


  // sort
  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    inline void
    __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
           _Compare __comp)
    {
      if (__first != __last)
        {
          std::__introsort_loop(__first, __last,
                                std::__lg(__last - __first) * 2,
                                __comp);
          std::__final_insertion_sort(__first, __last, __comp);
        }
    }

 

해당 함수에서는, 시작과 끝이 일치하지 않을때 introSort 재귀함수를 진행하고, 종료 시점에 삽입 정렬을 수행한다.

 

introsort_loop (Instro sort 재귀함수) 에서는, 미리 정해진 threadhold 상수값을 기준으로 정렬을 선택해서 사용한다.

 

  /// This is a helper function for the sort routine.
  template<typename _RandomAccessIterator, typename _Size, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    void
    __introsort_loop(_RandomAccessIterator __first,
                     _RandomAccessIterator __last,
                     _Size __depth_limit, _Compare __comp)
    {
      while (__last - __first > int(_S_threshold))
        {
          if (__depth_limit == 0)
            {
              std::__partial_sort(__first, __last, __last, __comp);
              return;
            }
          --__depth_limit;
          _RandomAccessIterator __cut =
            std::__unguarded_partition_pivot(__first, __last, __comp);
          std::__introsort_loop(__cut, __last, __depth_limit, __comp);
          __last = __cut;
        }
    }

 

_S_threadhold 라는 상수가 문제의 상수인데, 파일을 조금 뒤져보니 "16" 이란 값으로 임의로 박혀있었다.

왜 하필 16인지에 대해서는.... 더 찾아봐야할거같긴 한데 일단은 16이라니까 16이라고 보자.

 

Introsort_loop 의 로직은,

1. 리스트의 길이가 16 초과 일때 로직을 수행하고

2. depth limit가 0이 아니라면 -> depth limit를 1 줄이고, 임의 pivot을 선택한 후 instroSort를 반복해서 선택한다.

3. 여기서, depth limit는 함수 시작 시 2⌈ log₂(length) ⌉ (log 연산값의 정수 올림) 의 값을 가지고 시작한다.(해당 연산을 N번 반복하므로 정렬의 평균 속도가 O(n log₂n) 이 나오는것..)

4. 연산을 반복하다, depth limit가 0이 되었고 (= 연산의 깊이가 2⌈ log₂(length) ⌉  돌파시), 길이가 16이상일 시 힙 정렬을 수행한다.

 

  //introsort 내부의 힙 정렬
  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    inline void
    __partial_sort(_RandomAccessIterator __first,
                   _RandomAccessIterator __middle,
                   _RandomAccessIterator __last,
                   _Compare __comp)
    {
      std::__heap_select(__first, __middle, __last, __comp);
      std::__sort_heap(__first, __middle, __comp);
    }

 

5. 최종적으로 모든 introsort 재귀함수가 끝나면, 남은 값에 대해 삽입 정렬을 수행한다.

 

 

---

단순히 std::sort 가 퀵 정렬인줄 알고 찾아봤는데, 알고보니 퀵 정렬을 개선한 무언가였다는거는 조금 의외였다...

 

참고로, 해당 정렬의 속도는 대체로   O(n log⁡ n) 가 나온다고 알려져 있다.

 

하긴 퀵보단 좋아야지