Como implementar algoritmos de classificação clássicos em C ++ moderno?

O std::sortalgoritmo (e seus primos std::partial_sorte std::nth_element) da Biblioteca Padrão C ++ é, na maioria das implementações, uma combinação complicada e híbrida de algoritmos de classificação mais elementares , como classificação de seleção, classificação de inserção, classificação rápida, classificação de mesclagem ou classificação de pilha.

Há muitas perguntas aqui e em sites irmãos, como https://codereview.stackexchange.com/, relacionadas a bugs, complexidade e outros aspectos das implementações desses algoritmos de classificação clássicos. A maioria das implementações oferecidas consiste em loops brutos, usa manipulação de índice e tipos de concreto, e geralmente não são triviais para analisar em termos de correção e eficiência.

Pergunta : como os algoritmos de classificação clássica acima mencionados podem ser implementados usando o C ++ moderno?

• sem loops brutos , mas combinando os blocos de construção algorítmicos da Biblioteca Padrão de<algorithm>
• interface do iterador e uso de modelos em vez de manipulação de índice e tipos concretos
• Estilo C ++ 14 , incluindo a Biblioteca Padrão completa, bem como redutores de ruído sintáticos, como autoaliases de modelo, comparadores transparentes e lambdas polimórficas.

Notas :

• para obter referências adicionais sobre implementações de algoritmos de classificação, consulte Wikipedia , Rosetta Code ou http://www.sorting-algorithms.com/
• de acordo com as convenções de Sean Parent (slide 39), um loop bruto é muito formais longo que a composição de duas funções com um operador. Então, f(g(x));ou f(x); g(x);ou f(x) + g(x);não são loops de matérias, e nem são os loops em selection_sorte insertion_sortabaixo.
• Sigo a terminologia de Scott Meyers para denotar o C ++ 1y atual como C ++ 14 e para denotar C ++ 98 e C ++ 03 como C ++ 98, portanto, não me chame por isso.
• Conforme sugerido nos comentários de @Mehrdad, forneço quatro implementações como um Exemplo ao vivo no final da resposta: C ++ 14, C ++ 11, C ++ 98 e Boost e C ++ 98.
• A resposta em si é apresentada apenas em termos de C ++ 14. Onde relevante, indico as diferenças sintáticas e de biblioteca em que as várias versões de idiomas diferem.

Blocos de construção algorítmicos

Começamos montando os blocos de construção algorítmicos da Biblioteca Padrão:

#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

• as ferramentas do iterador, como não membro std::begin()e std::end()também std::next()estão disponíveis apenas a partir do C ++ 11 e além. Para o C ++ 98, é necessário escrevê-los ele mesmo. Existem substitutos do Boost.Range em boost::begin()/ boost::end()e do Boost.Utility em boost::next().
• o std::is_sortedalgoritmo está disponível apenas para C ++ 11 e além. Para o C ++ 98, isso pode ser implementado em termos de std::adjacent_finde um objeto de função manuscrita. O Boost.Algorithm também fornece boost::algorithm::is_sortedum substituto.
• o std::is_heapalgoritmo está disponível apenas para C ++ 11 e além.

Guloseimas sintáticas

O C ++ 14 fornece comparadores transparentes da forma std::less<>que agem polimorficamente em seus argumentos. Isso evita precisar fornecer o tipo de um iterador. Isso pode ser usado em combinação com os argumentos do modelo de função padrão do C ++ 11 para criar uma única sobrecarga para algoritmos de classificação que tomam <como comparação e aqueles que têm um objeto de função de comparação definido pelo usuário.

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

No C ++ 11, é possível definir um alias de modelo reutilizável para extrair o tipo de valor de um iterador, o que adiciona um pouco de confusão às assinaturas dos algoritmos de classificação:

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{});

No C ++ 98, é necessário escrever duas sobrecargas e usar a typename xxx<yyy>::typesintaxe detalhada

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>());
}

• Outra segurança sintática é que o C ++ 14 facilita o agrupamento de comparadores definidos pelo usuário por meio de lambdas polimórficas (com autoparâmetros deduzidos como argumentos de modelo de função).
• O C ++ 11 possui apenas lambdas monomórficas, que requerem o uso do alias do modelo acima value_type_t.
• No C ++ 98, é necessário escrever um objeto de função independente ou recorrer à sintaxe detalhada std::bind1st/ std::bind2nd/ std::not1.
• O Boost.Bind aprimora isso com a sintaxe boost::binde _1/ _2placeholder.
• C ++ 11 e além de também ter std::find_if_not, ao passo que C ++ 98 precisa std::find_ifcom um std::not1em torno de um objecto função.

Estilo C ++

Ainda não existe um estilo C ++ 14 geralmente aceitável. Para o bem ou para o mal, sigo de perto o rascunho de Scott Meyers, Effective Modern C ++ e o renovado GotW de Herb Sutter . Eu uso as seguintes recomendações de estilo:

• A recomendação "Quase sempre auto" de Herb Sutter e a opção "Preferir auto a declarações de tipo específicas " de Scott Meyers , para as quais a brevidade é insuperável, embora sua clareza às vezes seja contestada .
• O artigo "Distinguir ()e {}ao criar objetos", de Scott Meyers, e escolhe consistentemente a inicialização entre chaves em {}vez da boa e antiga inicialização entre parênteses ()(a fim de evitar todos os problemas de análise mais irritante no código genérico).
• Scott Meyers "Prefere declarações de alias a typedefs" . De qualquer forma, para os modelos, isso é obrigatório e usá-lo em qualquer lugar, em vez de typedefeconomizar tempo e adicionar consistência.
• Eu uso um for (auto it = first; it != last; ++it)padrão em alguns lugares, para permitir a verificação invariável de loop para subintervalos já classificados. No código de produção, o uso de while (first != last)e um ++firstlugar dentro do loop pode ser um pouco melhor.

Classificação da seleção

A classificação por seleção não se adapta aos dados de forma alguma, portanto seu tempo de execução é sempreO(N²). No entanto, a classificação de seleção tem a propriedade de minimizar o número de trocas . Em aplicativos em que o custo de troca de itens é alto, o tipo de seleção muito bem pode ser o algoritmo de escolha.

Para implementá-lo usando a Biblioteca Padrão, use repetidamente std::min_elementpara encontrar o elemento mínimo restante e iter_swaptroque-o no lugar:

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));
    }
}

Observe que selection_sorto intervalo já processado foi [first, it)classificado como invariante. Os requisitos mínimos são iteradores avançados , em comparação com std::sortos iteradores de acesso aleatório.

Detalhes omitidos :

• a classificação da seleção pode ser otimizada com um teste inicial if (std::distance(first, last) <= 1) return;(ou para iteradores diretos / bidirecionais:) if (first == last || std::next(first) == last) return;.
• para iteradores bidirecionais , o teste acima pode ser combinado com um loop no intervalo [first, std::prev(last)), porque o último elemento é garantido como o elemento restante mínimo e não requer troca.

Classificação de inserção

Embora seja um dos algoritmos de classificação elementar com O(N²)pior momento, a classificação por inserção é o algoritmo de escolha quando os dados são quase classificados (por serem adaptáveis ) ou quando o tamanho do problema é pequeno (por ter uma sobrecarga baixa). Por esses motivos, e como também é estável , a classificação por inserção é frequentemente usada como o caso base recursivo (quando o tamanho do problema é pequeno) para algoritmos de classificação de divisão e conquista de sobrecarga, como classificação de mesclagem ou classificação rápida.

Para implementar insertion_sortcom a Biblioteca padrão, use repetidamente std::upper_boundpara encontrar o local para onde o elemento atual precisa ir e use std::rotatepara deslocar os elementos restantes para cima no intervalo de entrada:

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));
    }
}

Observe que insertion_sorto intervalo já processado foi [first, it)classificado como invariante. A classificação por inserção também funciona com iteradores avançados.

Detalhes omitidos :

• a classificação de inserção pode ser otimizada com um teste inicial if (std::distance(first, last) <= 1) return;(ou para iteradores avançados / bidirecionais:) if (first == last || std::next(first) == last) return;e um loop no intervalo [std::next(first), last), porque o primeiro elemento é garantido para estar no lugar e não requer uma rotação.
• para iteradores bidirecionais , a pesquisa binária para encontrar o ponto de inserção pode ser substituída por uma pesquisa linear reversa usando o std::find_if_notalgoritmo da Biblioteca Padrão .

Quatro exemplos dinâmicos ( C ++ 14 , C ++ 11 , C ++ 98 e Boost , C ++ 98 ) para o fragmento abaixo:

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();

• Para entradas aleatórias, isso fornece O(N²)comparações, mas isso melhora as O(N)comparações para entradas quase ordenadas. A pesquisa binária sempre usa O(N log N)comparações.
• Para pequenos intervalos de entrada, a melhor localização da memória (cache, pré-busca) de uma pesquisa linear também pode dominar uma pesquisa binária (é preciso testar isso, é claro).

Ordenação rápida

Quando implementada com cuidado, a classificação rápida é robusta e tem O(N log N)complexidade esperada, mas com O(N²)complexidade de pior caso que pode ser acionada com dados de entrada escolhidos adversamente. Quando uma classificação estável não é necessária, a classificação rápida é uma excelente classificação de uso geral.

Mesmo para as versões mais simples, a classificação rápida é um pouco mais complicada de implementar usando a Biblioteca Padrão do que os outros algoritmos de classificação clássicos. A abordagem abaixo usa alguns utilitários do iterador para localizar o elemento do meio do intervalo de entrada [first, last)como o pivô e, em seguida, use duas chamadas para std::partition(que são O(N)) para particionar de três maneiras o intervalo de entrada em segmentos de elementos menores que, iguais a, e maior que o pivô selecionado, respectivamente. Finalmente, os dois segmentos externos com elementos menores e maiores que o pivô são classificados recursivamente:

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));
}

No entanto, a ordenação rápida é um pouco complicada para ser correta e eficiente, pois cada uma das etapas acima deve ser cuidadosamente verificada e otimizada para o código do nível de produção. Em particular, por O(N log N)complexidade, o pivô deve resultar em uma partição balanceada dos dados de entrada, que não podem ser garantidos em geral para um O(1)pivô, mas que podem ser garantidos se alguém definir o pivô como a O(N)mediana do intervalo de entrada.

Detalhes omitidos :

• a implementação acima é particularmente vulnerável a entradas especiais, por exemplo, possui O(N^2)complexidade para a entrada de " tubo de órgão " 1, 2, 3, ..., N/2, ... 3, 2, 1(porque o meio é sempre maior que todos os outros elementos).
• a seleção de pivô com mediana de 3 a partir de elementos escolhidos aleatoriamente na faixa de entrada protege contra entradas quase classificadas para as quais a complexidade se deteriorariaO(N^2).
• O particionamento de três vias (separar elementos menores que, iguais e maiores que o pivô), conforme mostrado pelas duas chamadas para,std::partitionnão é oO(N)algoritmomais eficientepara alcançar esse resultado.
• para iteradores de acesso aleatório , uma O(N log N)complexidade garantida pode ser alcançada através da seleção de mediana de pivô usando std::nth_element(first, middle, last), seguida de chamadas recursivas para quick_sort(first, middle, cmp)e quick_sort(middle, last, cmp).
• essa garantia tem um custo, no entanto, porque o fator constante da O(N)complexidade de std::nth_elementpode ser mais caro do que o da O(1)complexidade de um pivô com mediana de 3 seguido de uma O(N)chamada para std::partition(que é uma passagem de encaminhamento único amigável para cache) os dados).

Mesclar classificação

Se o uso de O(N)espaço extra não for motivo de preocupação, a classificação por mesclagem é uma excelente opção: é o único algoritmo de classificação estável O(N log N) .

É simples de implementar usando algoritmos Padrão: use alguns utilitários de iterador para localizar o meio do intervalo de entrada [first, last)e combinar dois segmentos classificados recursivamente com um 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));
}

A classificação de mesclagem requer iteradores bidirecionais, sendo o gargalo std::inplace_merge. Observe que, ao classificar listas vinculadas, a classificação por mesclagem requer apenas O(log N)espaço extra (para recursão). O último algoritmo é implementado std::list<T>::sortna Biblioteca Padrão.

Classificação da pilha

A classificação de heap é simples de implementar, executa uma classificaçãoO(N log N)no local, mas não é estável.

O primeiro loop, O(N)fase "heapify", coloca a matriz em ordem de heap. O segundo loop, a O(N log Nfase) "ordenação", extrai repetidamente o máximo e restaura a ordem do heap. A Biblioteca Padrão torna isso extremamente simples:

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));
}

Caso considere "trapaça" usar std::make_heape std::sort_heap, você pode ir um nível mais fundo e escrever essas funções em termos de std::push_heape std::pop_heap, respectivamente:

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

A Biblioteca padrão especifica tanto push_heape pop_heapcomo complexidade O(log N). Observe, no entanto, que o loop externo acima do intervalo [first, last)resulta em O(N log N)complexidade para make_heap, enquanto que std::make_heappossui apenas O(N)complexidade. Pois a O(N log N)complexidade geral heap_sortdisso não importa.

Detalhes omitidos : O(N)implementação demake_heap

Teste

Aqui estão quatro exemplos dinâmicos ( C ++ 14 , C ++ 11 , C ++ 98 e Boost , C ++ 98 ) testando todos os cinco algoritmos em uma variedade de entradas (não destinadas a ser exaustivas ou rigorosas). Observe as enormes diferenças no LOC: C ++ 11 / C ++ 14 precisa de cerca de 130 LOC, C ++ 98 e Boost 190 (+ 50%) e C ++ 98 mais de 270 (+ 100%).

Outro pequeno e bastante elegante originalmente encontrado na revisão de código . Eu pensei que valia a pena compartilhar.

Contando classificação

Embora seja bastante especializada, a ordenação por contagem é um algoritmo simples de ordenação de números inteiros e geralmente pode ser muito rápido, desde que os valores dos inteiros a serem ordenados não estejam muito distantes. Provavelmente é ideal se você precisar classificar uma coleção de um milhão de números inteiros que se sabe entre 0 e 100, por exemplo.

Para implementar uma classificação de contagem muito simples que funcione com números inteiros assinados e não assinados, é necessário encontrar os menores e maiores elementos da coleção a serem classificados; sua diferença indicará o tamanho da matriz de contagens a ser alocada. Em seguida, uma segunda passagem pela coleção é feita para contar o número de ocorrências de cada elemento. Finalmente, escrevemos novamente o número necessário de cada número inteiro para a coleção original.

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++);
    }
}

Embora seja útil apenas quando se sabe que o intervalo dos números inteiros a serem classificados é pequeno (geralmente não é maior que o tamanho da coleção a ser classificada), tornar a classificação da contagem mais genérica tornaria mais lenta para seus melhores casos. Se não for conhecido que o intervalo é pequeno, outro algoritmo, como radix sort , ska_sort ou spreadsort, pode ser usado.

Detalhes omitidos :

• Poderíamos ter ultrapassado os limites do intervalo de valores aceitos pelo algoritmo como parâmetros para se livrar totalmente da primeira std::minmax_elementpassagem pela coleção. Isso tornará o algoritmo ainda mais rápido quando um limite de alcance pequeno e útil for conhecido por outros meios. (Não precisa ser exato; passar uma constante de 0 a 100 ainda é muito melhor do que uma passagem extra de um milhão de elementos para descobrir que os limites verdadeiros são de 1 a 95. Até 0 a 1000 valeriam a pena; elementos extras são escritos uma vez com zero e lidos uma vez).

• Crescer countsrapidamente é outra maneira de evitar um primeiro passe separado. Dobrar o countstamanho cada vez que precisa crescer fornece tempo O (1) amortizado por elemento classificado (consulte a análise de custo de inserção da tabela de hash para a prova de que o crescimento exponencial é a chave). Crescer no final para um novo maxé fácil com std::vector::resizea adição de novos elementos zerados. Mudar rapidamente mine inserir novos elementos zerados na frente pode ser feito std::copy_backwardapós o crescimento do vetor. Em seguida, std::fillzere os novos elementos.

• O countsloop de incremento é um histograma. Se é provável que os dados sejam altamente repetitivos e o número de posições seja pequeno, vale a pena desenrolar sobre várias matrizes para reduzir o gargalo da dependência de dados de serialização de armazenar / recarregar na mesma bandeja. Isso significa mais contagens para zero no início e mais repetições no final, mas deve valer a pena na maioria das CPUs para o nosso exemplo de milhões de 0 a 100 números, especialmente se a entrada já puder ser (parcialmente) classificada e tem longas execuções do mesmo número.

• No algoritmo acima, usamos uma min == maxverificação para retornar mais cedo quando cada elemento tiver o mesmo valor (nesse caso, a coleção é classificada). Na verdade, é possível verificar totalmente se a coleção já está classificada e encontrar os valores extremos de uma coleção sem perder tempo adicional (se a primeira passagem ainda estiver com gargalo de memória com o trabalho extra de atualizar min e max). No entanto, esse algoritmo não existe na biblioteca padrão e escrever um seria mais tedioso do que escrever o resto da classificação em si. É deixado como um exercício para o leitor.

• Como o algoritmo funciona apenas com valores inteiros, asserções estáticas podem ser usadas para impedir que os usuários cometam erros de tipo óbvios. Em alguns contextos, uma falha de substituição com std::enable_if_tpode ser preferida.

• Enquanto o C ++ moderno é legal, o C ++ futuro pode ser ainda mais interessante: ligações estruturadas e algumas partes do Ranges TS tornariam o algoritmo ainda mais limpo.