std::sort와 std::list.sort

<algorithm>에서 제공하는 std::sort 함수는 지정된 조건에 맞게 정렬을 해주는 함수이다.

vector나 배열에서 사용은 많이 해보았을 것이라 생각한다. 그렇다면 std::sort는 과연 어떤 인자를 받고 있을까?

 

이 글에서는 std::sort의 작동방법과 왜 std::list에서는 사용할 수 없는지 알아보겠다.

(Visual Studio MSVC 기준이다.)

---

std::sort

 

이 함수는 헤더 파일에 다음과 같이 정의되어 있다.

_EXPORT_STD template <class _RanIt, class _Pr>
_CONSTEXPR20 void sort(const _RanIt _First, const _RanIt _Last, _Pr _Pred) { // order [_First, _Last)
    _Adl_verify_range(_First, _Last);
    const auto _UFirst = _Get_unwrapped(_First);
    const auto _ULast  = _Get_unwrapped(_Last);
    _Sort_unchecked(_UFirst, _ULast, _ULast - _UFirst, _Pass_fn(_Pred));
}

 

명시적으로 지정하지는 않았지만 이름으로 볼 때, Random Iterator를 사용하고 있다는 것을 알 수 있다.

 

그리고 _Sort_unchecked 메서드를 보면...

template <class _RanIt, class _Pr>
_CONSTEXPR20 void _Sort_unchecked(_RanIt _First, _RanIt _Last, _Iter_diff_t<_RanIt> _Ideal, _Pr _Pred) {
    // order [_First, _Last)
    for (;;) {
        if (_Last - _First <= _ISORT_MAX) { // small
            _Insertion_sort_unchecked(_First, _Last, _Pred);
            return;
        }

        if (_Ideal <= 0) { // heap sort if too many divisions
            _Make_heap_unchecked(_First, _Last, _Pred);
            _Sort_heap_unchecked(_First, _Last, _Pred);
            return;
        }

        // divide and conquer by quicksort
        auto _Mid = _Partition_by_median_guess_unchecked(_First, _Last, _Pred);

        _Ideal = (_Ideal >> 1) + (_Ideal >> 2); // allow 1.5 log2(N) divisions

        if (_Mid.first - _First < _Last - _Mid.second) { // loop on second half
            _Sort_unchecked(_First, _Mid.first, _Ideal, _Pred);
            _First = _Mid.second;
        } else { // loop on first half
            _Sort_unchecked(_Mid.second, _Last, _Ideal, _Pred);
            _Last = _Mid.first;
        }
    }
}

 

기본적으로 IntroSort 하이브리드 알고리즘을 사용하여 정렬을 하고 있는 것을 알 수 있다.

 

매우 크기가 작은 구조에 대해서는 유리한 삽입 정렬(Insertion Sort)를 사용하고 있고,

재귀가 깊어질 때 (_Ideal <= 0)는 힙 정렬(Heap Sort)를 사용하고 있는 것을 알 수 있다.

기본적으로는 pivot(_Mid)를 얻어 퀵 정렬(Quick Sort)를 사용하여 재귀 호출을 하고 있는 것을 알 수 있다.

(이전에는 퀵 정렬만 사용하고 있었지만, 최악의 경우 O(N^2)의 시간이 나오기 때문에 이렇게 하이브리드 알고리즘을 사용해서 최악의 경우에도 힙 정렬을 사용하여 O(N log N)의 시간이 나오도록 되었다.)

 

자, std::sort는 해당 내용을 실행 시킬 수 있으면, 해당 자료구조에 대해 이 함수를 사용할 수 있다는 것이다.

즉, Random Access Iterator가 가능한 컨테이너면 사용 가능하다는 뜻이다. 왜냐하면, sort 내부에서 임의 접근을 활용하기 때문이다.

한번 생각해보면 당연하기도 한 것 같다. 임의 접근이 가능하다는 것은 iterator에서 특정 값을 더하거나 빼서 해당 위치에 있는 값을 바로 얻을 수 있어야한다. (it += n 처럼) 그러나 linked list에서는 n번째 값을 얻으려면 꼬리를 물고 들어가서 n번의 시간이 걸리기 때문이다.

따라서 std::list는 std::sort에서 사용하는 알고리즘을 사용하면 굉장히 비효율적이라는 이야기가 된다.

 

우리가 흔히 사용하는 std::vector나 배열 등은 기본적으로 내부컨테이너로 임의 접근이 가능하게 되어 있다. 그러나 std::list는 알다시피 연결 리스트로 구성이 되어 있다.  그렇다면 std::list는 어떤 정렬을 이용할까?

---

std::list

 

std::list에서 std::sort 함수를 사용할 수 없다. std::list의 멤버함수로 sort를 제공하고 있다.

void sort() { // order sequence
    sort(less<>{});
}

template <class _Pr2>
void sort(_Pr2 _Pred) { // order sequence
    auto& _My_data = _Mypair._Myval2;
    _Scary_val::_Sort(_My_data._Myhead->_Next, _My_data._Mysize, _Pass_fn(_Pred));
}

template <class _Pr2>
static _Nodeptr _Sort(_Nodeptr& _First, const size_type _Size, _Pr2 _Pred) {
    // order [_First, _First + _Size), return _First + _Size
    switch (_Size) {
    case 0:
        return _First;
    case 1:
        return _First->_Next;
    default:
        break;
    }

    auto _Mid        = _Sort(_First, _Size / 2, _Pred);
    const auto _Last = _Sort(_Mid, _Size - _Size / 2, _Pred);
    _First           = _Merge_same(_First, _Mid, _Last, _Pred);
    return _Last;
}

template <class _Pr2>
static _Nodeptr _Merge_same(_Nodeptr _First, _Nodeptr _Mid, const _Nodeptr _Last, _Pr2 _Pred) {
    // Merge the sorted ranges [_First, _Mid) and [_Mid, _Last)
    // Returns the new beginning of the range (which won't be _First if it was spliced elsewhere)
    _STL_INTERNAL_CHECK(_First != _Mid && _Mid != _Last);
    _Nodeptr _Newfirst;
    if (_DEBUG_LT_PRED(_Pred, _Mid->_Myval, _First->_Myval)) {
        // _Mid will be spliced to the front of the range
        _Newfirst = _Mid;
    } else {
        // Establish _Pred(_Mid->_Myval, _First->_Myval) by skipping over elements from the first
        // range already in position.
        _Newfirst = _First;
        do {
            _First = _First->_Next;
            if (_First == _Mid) {
                return _Newfirst;
            }
        } while (!_DEBUG_LT_PRED(_Pred, _Mid->_Myval, _First->_Myval));
    }

    for (;;) { // process one run splice
        auto _Run_start = _Mid;
        do { // find the end of the "run" of elements we need to splice from the second range into the first
            _Mid = _Mid->_Next;
        } while (_Mid != _Last && _DEBUG_LT_PRED(_Pred, _Mid->_Myval, _First->_Myval));

        // [_Run_start, _Mid) goes before _First->_Myval
        _Unchecked_splice(_First, _Run_start, _Mid);
        if (_Mid == _Last) {
            return _Newfirst;
        }

        // Reestablish _Pred(_Mid->_Myval, _First->_Myval) by skipping over elements from the first
        // range already in position.
        do {
            _First = _First->_Next;
            if (_First == _Mid) {
                return _Newfirst;
            }
        } while (!_DEBUG_LT_PRED(_Pred, _Mid->_Myval, _First->_Myval));
    }
}

 

std::list.sort()는 병합 정렬 (Merge Sort)로 실행된다는 것을 알 수 있다!

std::list는 양방향 반복자(Bidirectional Iterator)를 제공하기 때문에 다른 std::deque나 std::vector와 같이 임의 접근이 불가능하다.

병합 정렬은 연결리스트의 양방향 반복자만으로도 효율적으로 정렬을 수행할 수 있다.

---

반복자 정리글은 다음을 참고하자

https://minttea25.tistory.com/130

STL 반복자와 연산 그리고 <algorithm> 헤더