Como implementar algoritmos clássicos de ordenação no moderno C ++?

O algoritmo std::sort (e seus primos std::partial_sort e std::nth_element ) da C ++ Standard Library é na maioria das implementações uma combinação complicada e híbrida de algoritmos de ordenação mais elementares , como sort sort, insertion sort, quick sort , merge sort, ou heap sort.

Há muitas perguntas aqui e em sites irmãos, como https://codereview.stackexchange.com/, relacionadas a bugs, complexidade e outros aspectos de implementações desses algoritmos de sorting clássicos. A maioria das implementações oferecidas consistem em loops crus, usam 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 clássicos de sorting mencionados acima podem ser implementados usando o moderno C ++?

  • sem loops crus , mas combinando os blocos de construção algorítmica da Biblioteca Padrão de
  • interface do iterador e uso de modelos em vez de manipulação de índice e tipos de concreto
  • Estilo C ++ 14 , incluindo a biblioteca padrão completa, bem como redutores de ruído sintático, como auto , aliases de modelo, comparadores transparentes e lambdas polimórficos.

Notas :

  • para mais referências sobre implementações de algoritmos de ordenação, veja Wikipedia , Rosetta Code ou http://www.sorting-algorithms.com/
  • de acordo com as convenções de Sean Parent (slide 39), um loop bruto é um loop mais longo que a composição de duas funções com um operador. Então f(g(x)); ou f(x); g(x); f(x); g(x); ou f(x) + g(x); não são loops crus, e nem os loops em selection_sort e insertion_sort abaixo.
  • Eu sigo a terminologia de Scott Meyers para denotar o atual C ++ 1y já como C ++ 14, e para denotar C ++ 98 e C ++ 03, ambos como C ++ 98, então não me chame para isso.
  • Como 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. Quando relevante, denote as diferenças sintáticas e de biblioteca onde as várias versões linguísticas diferem.

Blocos de construção algorítmicos

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

 #include  // min_element, iter_swap, // upper_bound, rotate, // partition, // inplace_merge, // make_heap, sort_heap, push_heap, pop_heap, // is_heap, is_sorted #include  // assert #include  // less #include  // distance, begin, end, next 
  • as ferramentas do iterador, como non-member std::begin() / std::end() , assim como std::next() só estão disponíveis a partir do C ++ 11 e posteriores. Para o C ++ 98, é preciso escrever isso sozinho. Existem substitutos de Boost.Range em boost::begin() / boost::end() e de Boost.Utility em boost::next() .
  • O algoritmo std::is_sorted está disponível apenas para C ++ 11 e posteriores. Para C ++ 98, isso pode ser implementado em termos de std::adjacent_find e um object de function escrito à mão. O Boost.Algorithm também fornece um boost::algorithm::is_sorted como um substituto.
  • O algoritmo std::is_heap está disponível apenas para C ++ 11 e posteriores.

Guloseimas sintéticas

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

 template> void xxx_sort(It first, It last, Compare cmp = Compare{}); 

Em C ++ 11, pode-se definir um alias de gabarito reutilizável para extrair o tipo de valor de um iterador que adiciona menor confusão às assinaturas dos algoritmos de sorting:

 template using value_type_t = typename std::iterator_traits::value_type; template>> void xxx_sort(It first, It last, Compare cmp = Compare{}); 

No C ++ 98, é preciso escrever duas sobrecargas e usar a syntax typename xxx::type detalhado

 template void xxx_sort(It first, It last, Compare cmp); // general implementation template void xxx_sort(It first, It last) { xxx_sort(first, last, std::less::value_type>()); } 
  • Uma outra subtileza sintática é que o C ++ 14 facilita o agrupamento de comparadores definidos pelo usuário por meio de lambdas polimórficos (com parâmetros auto que são deduzidos como argumentos de gabarito de function).
  • O C ++ 11 possui apenas lambdas monomórficos, que requerem o uso do alias do modelo acima value_type_t .
  • Em C ++ 98, é necessário escrever um object de function autônomo ou recorrer ao tipo de syntax std::bind1st / std::bind2nd / std::not1 std::bind2nd .
  • Boost.Bind melhora isso com boost::bind syntax de espaço reservado boost::bind e _1 / _2 .
  • C ++ 11 e além também possuem std::find_if_not , enquanto C ++ 98 precisa de std::find_if com um std::not1 torno de um object de function.

Estilo C ++

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

  • "Almost Always Always Auto", de Herb Sutter, e "Prefere declarações específicas de tipo" , de Scott Meyers, para as quais a brevidade é insuperável, embora sua clareza seja às vezes contestada .
  • "Distinguir () e {} ao criar objects" de Scott Meyers e escolher consistentemente a boot em órbita {} vez da boa e velha boot entre parênteses () (para acompanhar todos os problemas mais complicados do código genérico).
  • "Preferir declarações de alias para typedefs" de Scott Meyers. Para modelos, é uma obrigação de qualquer maneira, e usá-lo em todos os lugares em vez de typedef economiza tempo e adiciona consistência.
  • Eu uso um padrão for (auto it = first; it != last; ++it) em alguns lugares, para permitir a verificação invariante de loops para subintervalos já classificados. No código de produção, o uso de while (first != last) e um ++first algum lugar dentro do loop podem ser um pouco melhores.

Tipo de seleção

A sorting de seleção não se adapta aos dados de forma alguma, portanto, seu tempo de execução é sempre O(N²) . No entanto, o tipo de seleção tem a propriedade de minimizar o número de trocas . Em aplicações em que o custo de troca de itens é alto, o tipo de seleção pode ser o algoritmo escolhido.

Para implementá-lo usando a Biblioteca Padrão, use repetidamente std::min_element para encontrar o elemento mínimo restante e iter_swap para trocá-lo:

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

Note que selection_sort tem o intervalo já processado [first, it) classificado como seu invariante de loop. Os requisitos mínimos são iteradores progressivos , comparados aos iteradores de access random do std::sort .

Detalhes omitidos :

  • A sorting de seleção pode ser otimizada com um teste inicial if (std::distance(first, last) <= 1) return; (ou para iteradores forward / bidirecional: if (first == last || std::next(first) == last) return; ).
  • para iteradores bidirecionais , o teste acima pode ser combinado com um loop sobre o intervalo [first, std::prev(last)) , porque o último elemento é garantido como sendo o elemento remanescente mínimo e não requer uma troca.

Tipo de inserção

Embora seja um dos algoritmos de ordenação elementares com O(N²) pior, a ordenação por inserção é o algoritmo escolhido quando os dados são quase ordenados (porque é adaptativo ) ou quando o tamanho do problema é pequeno (porque tem baixa sobrecarga). Por essas razões, e porque também é estável , a sorting de inserção é frequentemente usada como o caso base recursivo (quando o tamanho do problema é pequeno) para algoritmos de sorting de divisão e conquista de sobrecarga superiores, como sorting por mesclagem ou sorting rápida.

Para implementar insertion_sort com a Biblioteca Padrão, use repetidamente std::upper_bound para encontrar o local onde o elemento atual precisa ir e use std::rotate para deslocar os elementos restantes para cima no intervalo de input:

 template> 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_sort tem o intervalo já processado [first, it) classificado como seu invariante de loop. A sorting de inserção também funciona com iteradores progressivos.

Detalhes omitidos :

  • A ordenação por inserção pode ser otimizada com um teste inicial if (std::distance(first, last) <= 1) return; (ou para iteradores forward / bidirecional: if (first == last || std::next(first) == last) return; ) e um loop sobre o 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 localizar o ponto de inserção pode ser substituída por uma pesquisa linear reversa usando o algoritmo std::find_if_not da Biblioteca Padrão.

Quatro exemplos ativos ( C ++ 14 , C ++ 11 , C ++ 98 e Boost , C ++ 98 ) para o fragment abaixo:

 using RevIt = std::reverse_iterator; auto const insertion = std::find_if_not(RevIt(it), RevIt(first), [=](auto const& elem){ return cmp(*it, elem); } ).base(); 
  • Para inputs aleatórias, isso fornece comparações O(N²) , mas isso melhora as comparações O(N) para inputs quase ordenadas. A pesquisa binária sempre usa comparações O(N log N) .
  • Para pequenos intervalos de input, a melhor localização de memory (cache, pré-busca) de uma pesquisa linear também pode dominar uma pesquisa binária (é necessário testar isso, é claro).

Ordenação rápida

Quando cuidadosamente implementada, a ordenação rápida é robusta e tem complexidade esperada de O(N log N) , mas com a complexidade do pior caso de O(N²) que pode ser triggersda com dados de input selecionados adversariamente. Quando uma sorting estável não é necessária, a sorting rápida é uma excelente sorting de propósito geral.

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

 template> 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 sorting rápida é bastante complicada para ser correta e eficiente, pois cada uma das etapas acima deve ser cuidadosamente verificada e otimizada para o código de nível de produção. Em particular, para a complexidade O(N log N) , o pivô tem que resultar em uma partição balanceada dos dados de input, que não pode ser garantida em geral para um pivô O(1) , mas que pode ser garantida se definirmos o pivô como a mediana O(N) do intervalo de input.

Detalhes omitidos :

  • a implementação acima é particularmente vulnerável a inputs especiais, por exemplo, tem complexidade O(N^2) para a input " pipe pipe " 1, 2, 3, ..., N/2, ... 3, 2, 1 ( porque o meio é sempre maior que todos os outros elementos).
  • a seleção de pivô de mediana de 3 a partir de elementos escolhidos aleatoriamente da faixa de input protege contra inputs quase classificadas para as quais a complexidade, de outra forma, se deterioraria para O(N^2) .
  • O particionamento de 3 vias (separando elementos menores, iguais e maiores que o pivot) como mostrado pelas duas chamadas para std::partition não é o algoritmo O(N) mais eficiente para alcançar este resultado.
  • para iteradores de access random , uma complexidade O(N log N) garantida pode ser obtida através da seleção mediana de pivô usando std::nth_element(first, middle, last) , seguido por chamadas recursivas a quick_sort(first, middle, cmp) e quick_sort(middle, last, cmp) .
  • essa garantia tem um custo, no entanto, porque o fator constante da complexidade O(N) do std::nth_element pode ser mais caro que o da complexidade O(1) de um pivô médio de 3 seguido por um O(N) chamada para std::partition (que é um único encaminhamento direto para cache sobre os dados).

Merge sort

Se usar O(N) espaço extra não é uma preocupação, então merge sort é uma excelente escolha: é o único algoritmo de ordenação O(N log N) estável .

É simples implementar usando algoritmos padrão: use alguns utilitários iteradores para localizar o meio do intervalo de input [first, last) e combinar dois segmentos ordenados recursivamente com um std::inplace_merge :

 template> 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 ordenação por mesclagem requer iteradores bidirecionais, sendo o gargalo o std::inplace_merge . Observe que ao classificar listas vinculadas, a sorting por mesclagem requer apenas o espaço extra O(log N) (para recursion). O último algoritmo é implementado por std::list::sort na biblioteca padrão.

Tipo de pilha

O ordenamento de heap é simples de implementar, executa uma sorting O(N log N) no local, mas não é estável.

O primeiro loop, a fase O(N) "heap", coloca o array em ordem de heap. O segundo loop, a fase de "ordenação" de O(N log N ), extrai repetidamente o máximo e restaura a ordem de heap. A biblioteca padrão torna isso extremamente simples:

 template> 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 você considere "trapaça" usar std::make_heap e std::sort_heap , você pode ir um nível mais profundo e escrever essas funções você mesmo em termos de std::push_heap e std::pop_heap , respectivamente:

 namespace lib { // NOTE: is O(N log N), not O(N) as std::make_heap template> 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> 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 push_heap e pop_heap como complexidade O(log N) . No entanto, observe que o loop externo no intervalo [first, last) resulta na complexidade de O(N log N) para make_heap , enquanto std::make_heap tem apenas a complexidade O(N) . Para a complexidade geral do O(N log N) do heap_sort , não importa.

Detalhes omitidos : O(N) implementação de make_heap

Testando

Aqui estão quatro Live Examples ( C ++ 14 , C ++ 11 , C ++ 98 e Boost , C ++ 98 ) testando todos os cinco algoritmos em uma variedade de inputs (não pretendendo ser exaustivas ou rigorosas). Apenas note que as grandes diferenças no LOC: C ++ 11 / C ++ 14 precisam de cerca de 130 LOC, C ++ 98 e Boost 190 (+ 50%) e C ++ 98 mais de 270 (+ 100%).

Outra pequena e bastante elegante originalmente encontrada na revisão de código . Eu pensei que valesse a pena compartilhar.

Contagem de tipo

Embora seja bastante especializado, a contagem de ordenação é um algoritmo simples de ordenação de números inteiros e muitas vezes pode ser realmente rápido desde que os valores dos inteiros para classificar não sejam muito distantes. É provavelmente ideal se alguém precisar classificar uma coleção de um milhão de inteiros conhecidos entre 0 e 100, por exemplo.

Para implementar uma sorting contável muito simples que funcione com números inteiros assinados e não assinados, é necessário encontrar os menores e maiores elementos na coleção para classificar; sua diferença dirá o tamanho da matriz de contagens a serem alocadas. Então, uma segunda passagem pela coleção é feita para contar o número de ocorrências de cada elemento. Por fim, escrevemos o número necessário de cada número inteiro de volta à coleção original.

 template 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::difference_type; std::vector 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 o intervalo de inteiros para classificar é conhecido como pequeno (geralmente não maior que o tamanho da coleção a ser classificada), tornar a sorting mais genérica tornaria mais lento para os melhores casos. Se o intervalo não é conhecido por ser pequeno, outro algoritmo, como radix sort , ska_sort ou spreadsort, pode ser usado em seu lugar.

Detalhes omitidos :

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

  • Crescer counts na mosca é outra maneira de evitar uma primeira passagem separada. Dobrar o tamanho das counts cada vez que ele tem que crescer dá O (1) tempo amortizado por elemento ordenado (veja a análise de custo de inserção de tabela de hash para a prova de que exponencial é a chave). Crescer no final para um novo max é fácil com std::vector::resize para adicionar novos elementos zerados. Mudar min on the fly e inserir novos elementos zerados na frente pode ser feito com std::copy_backward após o crescimento do vetor. Então std::fill para zerar os novos elementos.

  • O loop de incremento de counts é um histograma. Se os dados provavelmente forem altamente repetitivos e o número de bins for pequeno, pode valer a pena desenrolá- los em vários arrays para reduzir o afunilamento de dependência de dados de serialização de armazenamento / recarregamento para o mesmo escaninho. Isso significa mais contagens para zero no início, e mais para fazer um loop no final, mas deve valer a pena na maioria das CPUs para nosso exemplo de milhões de 0 a 100 números, especialmente se a input já puder ser (parcialmente) classificada e tem corridas longas do mesmo número.

  • No algoritmo acima, usamos uma verificação min == max 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 enquanto encontra os valores extremos de uma coleção sem tempo adicional desperdiçado (se a primeira passagem ainda for memory afunilada com o trabalho extra de atualização de min e max). No entanto, tal algoritmo não existe na biblioteca padrão e escrever um seria mais tedioso do que escrever o resto da contagem em si. É deixado como um exercício para o leitor.

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

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

Intereting Posts