[c++] 현대 C ++에서 고전적인 정렬 알고리즘을 구현하는 방법은 무엇입니까?

알고리즘 빌딩 블록

우리는 표준 라이브러리에서 알고리즘 빌딩 블록을 조립하는 것으로 시작합니다.

#include <algorithm>    // min_element, iter_swap, 
                        // upper_bound, rotate, 
                        // partition, 
                        // inplace_merge,
                        // make_heap, sort_heap, push_heap, pop_heap,
                        // is_heap, is_sorted
#include <cassert>      // assert 
#include <functional>   // less
#include <iterator>     // distance, begin, end, next

• 반복자 같은 비회원 같은 도구 std::begin()/ std::end()뿐만와 마찬가지로는 std::next()11 년 이후 ++ C의 등 만 사용할 수 있습니다. C ++ 98의 경우 직접 작성해야합니다. Boost.Range in boost::begin()/ boost::end()및 Boost.Utility in 대체 항목이 boost::next()있습니다.
• std::is_sorted알고리즘은 11 년 이후 ++ C에만 사용할 수 있습니다. C ++ 98의 경우이 std::adjacent_find기능은 직접 작성하는 함수 객체 로 구현할 수 있습니다 . Boost.Algorithm은 또한 boost::algorithm::is_sorted대용으로 제공합니다 .
• std::is_heap알고리즘은 11 년 이후 ++ C에만 사용할 수 있습니다.

구문 적 장점

C ++ 14는 인수에 대해 다형성으로 작동 하는 형식의 투명한 비교기 를 제공합니다 std::less<>. 이것은 반복자 유형을 제공하지 않아도됩니다. 이를 C ++ 11의 기본 함수 템플릿 인수 와 함께 사용하여 비교 알고리즘 과 사용자 정의 비교 함수 객체가있는 정렬 알고리즘을위한 단일 과부하 를 만들 수 있습니다 <.

template<class It, class Compare = std::less<>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

C ++ 11에서는 재사용 가능한 템플릿 별명 을 정의 하여 정렬 알고리즘의 서명에 작은 혼란을 추가하는 반복자의 값 유형을 추출 할 수 있습니다 .

template<class It>
using value_type_t = typename std::iterator_traits<It>::value_type;

template<class It, class Compare = std::less<value_type_t<It>>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

C ++ 98에서는 두 개의 오버로드를 작성하고 자세한 typename xxx<yyy>::type구문을 사용해야 합니다.

template<class It, class Compare>
void xxx_sort(It first, It last, Compare cmp); // general implementation

template<class It>
void xxx_sort(It first, It last)
{
    xxx_sort(first, last, std::less<typename std::iterator_traits<It>::value_type>());
}

• 또 다른 구문상의 장점은 C ++ 14가 다형성 람다 ( auto함수 템플릿 인수와 같이 추론 되는 매개 변수 포함)를 통해 사용자 정의 비교기를 래핑하는 것을 용이하게 한다는 것입니다.
• C ++ 11에는 단형 람다 만 있으며 위의 템플릿 별칭을 사용해야합니다 value_type_t.
• C ++ 98에서는 독립형 함수 객체를 작성하거나 verbose std::bind1st/ std::bind2nd/ std::not1유형의 구문을 사용해야합니다.
• Boost.Bind는 boost::bind및 _1/ _2자리 표시 자 구문 으로이 기능을 향상시킵니다 .
• C ++ 11도 이상이 std::find_if_notC ++ 98 개 반면 요구 std::find_ifA의 std::not1함수 객체 주변.

C ++ 스타일

일반적으로 허용되는 C ++ 14 스타일은 아직 없습니다. 더 좋든 나쁘 든 나는 Scott Meyers의 Effective Modern C ++ 초안 과 Herb Sutter의 개선 된 GotW를 밀접하게 따릅니다 . 다음과 같은 스타일 권장 사항을 사용합니다.

• 허브 셔터의 “거의 항상 자동” 스콧 마이어스의는 “특정 유형의 선언에 자동 안함” 선명도가 종종 있지만, 간결은 타의 추종을 불허하는 추천, 이의를 제기 .
• Scott Meyers의 ” 객체를 구별 ()하고 {}작성할 때”를 사용 하고 {}기존의 괄호로 묶은 초기화 대신 일관된 초기화 를 선택하십시오 ()(일반 코드에서 모든 가장 절박한 구문 분석 문제를 회피하기 위해).
• Scott Meyers의 “별칭 선언을 typedefs 선호” . 템플릿의 경우 어쨌든 필수이며, typedef시간 을 절약하고 일관성을 추가하는 대신 어디에서나 사용하면 됩니다.
• for (auto it = first; it != last; ++it)이미 정렬 된 하위 범위에 대한 루프 불변 검사를 허용하기 위해 일부 장소에서 패턴을 사용 합니다. 프로덕션 코드에서는 루프 내부 while (first != last)와 ++first어딘가 의 사용 이 약간 더 좋습니다.

선택 정렬

선택 정렬 은 어떤 식 으로든 데이터에 적용되지 않으므로 런타임은 항상O(N²)입니다. 그러나 선택 정렬에는 스왑 수를 최소화하는 속성이있습니다. 아이템 교환 비용이 높은 애플리케이션에서는 선택 정렬이 매우 적합한 알고리즘 일 수 있습니다.

표준 라이브러리를 사용하여 구현하려면 반복해서 사용 std::min_element하여 나머지 최소 요소를 찾아서 iter_swap교체하십시오.

template<class FwdIt, class Compare = std::less<>>
void selection_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const selection = std::min_element(it, last, cmp);
        std::iter_swap(selection, it);
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

참고 selection_sort이미 처리 범위를 갖는다는 [first, it)그 루프 불변으로 정렬. 최소 요구 사항은 임의 액세스 반복기 와 비교하여 순방향std::sort 반복기입니다.

세부 사항 생략 :

• 선택 정렬은 초기 테스트 if (std::distance(first, last) <= 1) return;(또는 순방향 / 양방향 반복자 if (first == last || std::next(first) == last) return;) 로 최적화 할 수 있습니다 .
• 위한 양방향 반복자 , 상기 시험이 간격 동안, 루프와 결합 될 수있는 [first, std::prev(last))마지막 요소가 최소한의 나머지 요소를 보장하고 스왑을 요구하지 않기 때문이다.

삽입 정렬

O(N²)시간 이 최악 인 기본 정렬 알고리즘 중 하나이지만 삽입 정렬 은 데이터가 거의 정렬 되거나 ( 적응성 이 있기 때문에 ) 문제 크기가 작을 때 (오버 헤드가 낮기 때문에) 선택한 알고리즘입니다 . 이러한 이유로, 또한 안정적 이기 때문에 삽입 정렬은 종종 병합 정렬 또는 빠른 정렬과 같은 더 높은 오버 헤드 분할 및 정복 정렬 알고리즘을위한 재귀 기본 사례 (문제 크기가 작은 경우)로 사용됩니다.

insertion_sort표준 라이브러리를 사용 std::upper_bound하여 구현하려면 반복해서 사용 하여 현재 요소가 필요한 위치를 찾고 std::rotate나머지 요소를 입력 범위에서 위로 이동하십시오.

template<class FwdIt, class Compare = std::less<>>
void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const insertion = std::upper_bound(first, it, *it, cmp);
        std::rotate(insertion, it, std::next(it));
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

참고 insertion_sort이미 처리 범위를 갖는다는 [first, it)그 루프 불변으로 정렬. 삽입 정렬은 순방향 반복자와도 작동합니다.

세부 사항 생략 :

• 삽입 정렬은 첫 번째 요소가 제자리에 있고 회전이 필요하지 않기 때문에 초기 테스트 if (std::distance(first, last) <= 1) return;(또는 순방향 / 양방향 반복자 🙂 if (first == last || std::next(first) == last) return;및 간격에 대한 루프 로 최적화 할 수 있습니다 [std::next(first), last).
• 대한 양방향 반복자 , 삽입 지점을 찾을 수있는 이진 검색은 교체 할 수 있습니다 역 선형 검색 표준 라이브러리의 사용 std::find_if_not알고리즘을.

아래 조각에 대한 4 가지 라이브 예제 ( C ++ 14 , C ++ 11 , C ++ 98 및 Boost , C ++ 98 ) :

using RevIt = std::reverse_iterator<BiDirIt>;
auto const insertion = std::find_if_not(RevIt(it), RevIt(first),
    [=](auto const& elem){ return cmp(*it, elem); }
).base();

• 무작위 입력의 경우 O(N²)비교가 이루어 지지만 O(N)거의 정렬 된 입력의 비교가 향상됩니다 . 이진 검색은 항상 O(N log N)비교를 사용합니다 .
• 작은 입력 범위의 경우 선형 검색의 메모리 지역성 (캐시, 프리 페치)이 이진 검색을 지배 할 수 있습니다 (물론이를 테스트해야 함).

빠른 정렬

신중하게 구현할 때 빠른 정렬 은 강력하고 O(N log N)복잡 할 것으로 예상되지만, O(N²)최악의 경우 복잡성이 발생하여 악의적으로 선택된 입력 데이터로 트리거 될 수 있습니다. 안정적인 정렬이 필요하지 않은 경우 빠른 정렬은 탁월한 범용 정렬입니다.

가장 간단한 버전의 경우에도 빠른 정렬은 다른 클래식 정렬 알고리즘보다 표준 라이브러리를 사용하여 구현하기가 훨씬 더 복잡합니다. 사용하는 몇 반복자 유틸리티 아래 방법은 찾아 중간 소자 의 입력 범위를 [first, last)다음 피벗로 두 통화 사용 std::partition(있는 O(N)보다 작은 소자의 세그먼트로 삼방 파티션)의 입력 범위를 같 선택한 피벗보다 각각 더 큽니다. 마지막으로 피벗보다 작거나 큰 요소가있는 두 개의 외부 세그먼트가 재귀 적으로 정렬됩니다.

template<class FwdIt, class Compare = std::less<>>
void quick_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;
    auto const pivot = *std::next(first, N / 2);
    auto const middle1 = std::partition(first, last, [=](auto const& elem){
        return cmp(elem, pivot);
    });
    auto const middle2 = std::partition(middle1, last, [=](auto const& elem){
        return !cmp(pivot, elem);
    });
    quick_sort(first, middle1, cmp); // assert(std::is_sorted(first, middle1, cmp));
    quick_sort(middle2, last, cmp);  // assert(std::is_sorted(middle2, last, cmp));
}

그러나 위의 각 단계를 신중하게 검사하고 프로덕션 레벨 코드에 맞게 최적화해야하기 때문에 빠른 정렬은 정확하고 효율적으로 얻기가 다소 까다 롭습니다. 특히, O(N log N)복잡성을 위해 , 피벗은 입력 데이터의 균형 잡힌 파티션을 초래해야하며, O(1)피벗에 대해 일반적 으로 보장 될 수 없지만 피벗을 O(N)입력 범위 의 중앙값 으로 설정하면 보장 될 수있다 .

세부 사항 생략 :

• 위의 구현은 특수 입력에 특히 취약합니다. 예를 들어 O(N^2)” 오르간 파이프 “입력 에는 복잡성 이 있습니다 1, 2, 3, ..., N/2, ... 3, 2, 1(중간이 항상 다른 모든 요소보다 크기 때문에).
• 입력 범위에서 무작위로 선택된 요소 에서 3 개의 중심 피벗을 선택하면 복잡성이 악화 될 수있는 거의 정렬 된 입력으로부터 보호됩니다O(N^2).
• 두 번의 호출로 표시되는 3 방향 파티셔닝 (피벗보다 작거나 같고 큰 요소를 분리)은이 결과를 얻는 데std::partition가장 효율적인O(N)알고리즘이 아닙니다.
• 위한 랜덤 액세스 반복자 , 보장 된 O(N log N)복잡성으로 달성 될 수있는 중간 피봇 선택 하여 std::nth_element(first, middle, last)재귀 호출 한 후, quick_sort(first, middle, cmp)그리고 quick_sort(middle, last, cmp).
• 그러나 이러한 O(N)복잡성의 상수 요소는 3 중위 피벗 std::nth_element의 O(1)복잡성에 대한 O(N)호출보다 다음에 대한 호출 std::partition(캐시 친화적 인 단일 전달) 보다 비용이 많이 들기 때문에 비용이 발생합니다. 자료).

정렬 병합

사용하는 경우 O(N)여분의 공간 것이 더 문제입니다, 다음 종류의 병합 탁월한 선택입니다 :가 아니라 안정적인 O(N log N) 정렬 알고리즘.

표준 알고리즘을 사용하여 간단하게 구현할 수 있습니다. 몇 가지 반복기 유틸리티를 사용하여 입력 범위의 중간을 찾고 [first, last)두 개의 재귀 적으로 정렬 된 세그먼트를 다음과 결합하십시오 std::inplace_merge.

template<class BiDirIt, class Compare = std::less<>>
void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;
    auto const middle = std::next(first, N / 2);
    merge_sort(first, middle, cmp); // assert(std::is_sorted(first, middle, cmp));
    merge_sort(middle, last, cmp);  // assert(std::is_sorted(middle, last, cmp));
    std::inplace_merge(first, middle, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

병합 정렬에는 양방향 반복기가 필요하며 병목 현상은 std::inplace_merge입니다. 연결된 목록을 정렬 할 때 병합 정렬에는 O(log N)추가 공간 만 필요합니다 (재귀 용). 후자의 알고리즘은 std::list<T>::sort표준 라이브러리에서 구현됩니다 .

힙 정렬

힙 정렬 은 구현하기 쉽고O(N log N)인플레 이스 정렬을수행하지만 안정적이지 않습니다.

첫 번째 루프 인 O(N)“heapify”단계는 배열을 힙 순서로 만듭니다. 두 번째 루프 인 O(N log N) “정렬”단계는 반복적으로 최대 값을 추출하고 힙 순서를 복원합니다. 표준 라이브러리는 이것을 매우 간단하게 만듭니다.

template<class RandomIt, class Compare = std::less<>>
void heap_sort(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    lib::make_heap(first, last, cmp); // assert(std::is_heap(first, last, cmp));
    lib::sort_heap(first, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

경우에 당신은 그것을 사용하는 “부정 행위”생각 std::make_heap하고 std::sort_heap당신이 한 단계 더 가서 측면에서 이러한 함수를 직접 작성 수 std::push_heap와 std::pop_heap각각 :

namespace lib {

// NOTE: is O(N log N), not O(N) as std::make_heap
template<class RandomIt, class Compare = std::less<>>
void make_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last;) {
        std::push_heap(first, ++it, cmp);
        assert(std::is_heap(first, it, cmp));
    }
}

template<class RandomIt, class Compare = std::less<>>
void sort_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = last; it != first;) {
        std::pop_heap(first, it--, cmp);
        assert(std::is_heap(first, it, cmp));
    }
}

}   // namespace lib

표준 라이브러리를 모두 지정 push_heap및 pop_heap복잡도를 O(log N). 그러나 범위에 대한 외부 루프는에 대한 복잡성을 [first, last)초래 하지만 복잡성 만 있습니다. 전체적인 복잡성에 대해서는 중요하지 않습니다.O(N log N)make_heapstd::make_heapO(N)O(N log N)heap_sort

생략 된 내용 : O(N)구현make_heap

테스팅

다음은 다양한 입력에 대해 5 가지 알고리즘을 테스트 하는 4 가지 라이브 예제 ( C ++ 14 , C ++ 11 , C ++ 98 및 Boost , C ++ 98 )입니다 (완전하거나 엄격한 것은 아님). LOC의 큰 차이점에 주목하십시오 .C ++ 11 / C ++ 14에는 약 130 개의 LOC, C ++ 98 및 Boost 190 (+ 50 %) 및 C ++ 98이 270 (+ 100 %) 이상 필요합니다.

답변

template<typename ForwardIterator>
void counting_sort(ForwardIterator first, ForwardIterator last)
{
    if (first == last || std::next(first) == last) return;

    auto minmax = std::minmax_element(first, last);  // avoid if possible.
    auto min = *minmax.first;
    auto max = *minmax.second;
    if (min == max) return;

    using difference_type = typename std::iterator_traits<ForwardIterator>::difference_type;
    std::vector<difference_type> counts(max - min + 1, 0);

    for (auto it = first ; it != last ; ++it) {
        ++counts[*it - min];
    }

    for (auto count: counts) {
        first = std::fill_n(first, count, min++);
    }
}