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

C ++ 표준 라이브러리 의 std::sort알고리즘 (및 그 사촌 std::partial_sortstd::nth_element)은 대부분의 구현 에서 선택 정렬, 삽입 정렬, 빠른 정렬, 병합 정렬 또는 힙 정렬과 같은 보다 기본적인 정렬 알고리즘의 복잡하고 하이브리드 화 된 통합입니다 .

여기에 그리고 https://codereview.stackexchange.com/ 과 같은 자매 사이트 에 이러한 고전적인 정렬 알고리즘의 구현, 버그, 복잡성 및 기타 측면과 관련된 많은 질문이 있습니다 . 제공된 구현의 대부분은 원시 루프로 구성되며 인덱스 조작 및 구체적인 유형을 사용하며 정확성과 효율성 측면에서 분석하기에는 일반적이지 않습니다.

질문 : 위에서 언급 한 클래식 정렬 알고리즘을 최신 C ++를 사용하여 어떻게 구현할 수 있습니까?

  • 원시 루프 는 없지만 표준 라이브러리의 알고리즘 빌딩 블록을 결합합니다.<algorithm>
  • 인덱스 조작 및 구체적인 유형 대신 반복자 인터페이스템플리트 사용
  • 전체 표준 라이브러리를 포함한 C ++ 14 스타일 , auto템플릿 별명, 투명 비교기 및 다형성 람다와 같은 구문 노이즈 감소 기 .

참고 사항 :

  • 정렬 알고리즘 구현에 대한 자세한 내용은 Wikipedia , Rosetta Code 또는 http://www.sorting-algorithms.com/을 참조하십시오.
  • 숀 부모의 규칙 (슬라이드 39), 원료 루프는 인 for-loop 이상 오퍼레이터 두 함수의 조성물보다. 그래서 f(g(x));f(x); g(x);또는 f(x) + g(x);원시 루프하지 않고, 어느 쪽도에서 루프없는 selection_sortinsertion_sort아래는.
  • 나는 Scott Meyers의 용어에 따라 현재 C ++ 1 y를 이미 C ++ 14로 표시하고 C ++ 98과 C ++ 03을 모두 C ++ 98로 표시하므로 화를 내지 마십시오.
  • @Mehrdad의 의견에서 제안한 것처럼 답변 끝에 C ++ 14, C ++ 11, C ++ 98 및 Boost 및 C ++ 98의 네 가지 구현을 라이브 예제로 제공합니다.
  • 답변 자체는 C ++ 14로만 제공됩니다. 관련이있는 경우, 다양한 언어 버전이 다른 구문 및 라이브러리 차이점을 나타냅니다.


답변

알고리즘 빌딩 블록

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

#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_elementO(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_heapstd::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_heappop_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 %) 이상 필요합니다.


답변

코드 검토에서 원래 발견 된 또 다른 작고 우아한 것 입니다. 공유 할 가치가 있다고 생각했습니다.

카운팅 정렬

다소 전문화되어 있지만 계산 정렬 은 간단한 정수 정렬 알고리즘이며 정렬 할 정수 값이 너무 멀지 않은 경우 종종 실제로 빠를 수 있습니다. 예를 들어 0에서 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++);
    }
}

정렬 할 정수의 범위가 작은 경우 (일반적으로 정렬 할 콜렉션의 크기보다 크지 않은 경우)에만 유용하지만 정렬을보다 일반적으로 계산하면 최상의 경우 속도가 느려집니다. 범위가 작지 않다면 기수 정렬 , ska_sort 또는 spreadsort 와 같은 다른 알고리즘을 대신 사용할 수 있습니다.

세부 사항 생략 :

  • std::minmax_element컬렉션을 통한 첫 번째 통과 를 완전히 없애기 위해 알고리즘에서 매개 변수로 허용되는 값 범위의 경계를 넘을 수있었습니다 . 이렇게하면 다른 방법으로 유용하게 작은 범위 제한이 알려진 경우 알고리즘이 더 빨라집니다. (정확할 필요는 없습니다. 상수 0 ~ 100을 전달하는 것이 백만 요소를 초과하는 추가 패스보다 훨씬 낫습니다. 실제 경계가 1 ~ 95임을 알 수 있습니다. 0 ~ 1000조차도 가치가 있습니다. 추가 요소는 0으로 한 번 쓰고 한 번 읽습니다).

  • counts즉석에서 성장하는 것은 별도의 첫 패스를 피하는 또 다른 방법입니다. counts크기가 커질 때마다 크기를 두 배로 늘리면 정렬 된 요소 당 상각 된 O (1) 시간이 발생합니다 (지수 증가가 핵심이라는 증거는 해시 테이블 삽입 비용 분석 참조). 새로운 영점 요소를 추가 하면 새로운 끝 부분을 max쉽게 확장 할 std::vector::resize수 있습니다. 벡터를 성장시킨 후 min즉석에서 변경 하고 전면에 새로운 영점 요소를 삽입 할 수 있습니다 std::copy_backward. 그런 다음 std::fill새 요소를 0으로 만듭니다.

  • counts증분 루프 히스토그램이다. 데이터가 반복성이 높고 빈 수가 적을 경우 여러 저장소를 롤링 하여 동일한 빈에 대한 저장소 / 재로드의 직렬화 데이터 종속성 병목 현상을 줄이는 것이 좋습니다. 즉, 시작시 더 많은 카운트가 0이고 끝에서 반복되는 것이 더 많지만, 특히 입력이 이미 (부분적으로) 정렬되고 같은 수의 장기 실행이 있습니다.

  • 위의 알고리즘에서, 우리 min == max는 모든 요소가 같은 값을 가질 때 조기에 리턴 하기 위해 체크를 사용 합니다 (이 경우 컬렉션이 정렬됩니다). 실제로 추가 시간 낭비없이 컬렉션의 극단적 인 값을 찾는 동안 컬렉션이 이미 정렬되어 있는지 완전히 확인할 수 있습니다 (첫 번째 패스가 여전히 최소 및 최대 업데이트 작업으로 인해 메모리 병목 현상이 발생하는 경우). 그러나 이러한 알고리즘은 표준 라이브러리에 존재하지 않으므로 나머지 계산 자체를 작성하는 것보다 지루할 것입니다. 독자를위한 연습으로 남겨둔다.

  • 이 알고리즘은 정수 값으로 만 작동하므로 정적 어설 션을 사용하여 사용자가 명백한 유형의 실수를 저 지르지 못하게 할 수 있습니다. 일부 상황에서는 대체 실패 std::enable_if_t가 선호 될 수 있습니다.

  • 현대적인 C ++은 멋지지만 미래의 C ++는 훨씬 더 시원 할 수 있습니다. 구조적 바인딩Ranges TS 의 일부 는 알고리즘을 더욱 깨끗하게 만들 것입니다.


답변