Qual algoritmo de sorting funciona melhor na maioria dos dados classificados?

Qual algoritmo de sorting funciona melhor na maioria dos dados classificados?

Baseado no método altamente científico de assistir gifs animados, eu diria que os tipos Inserção e Bolha são bons candidatos.

Apenas alguns itens => INSERTION SORT

Itens são principalmente classificados já => INSERTION SORT

Preocupado com os piores cenários => HEAP SORT

Interessado em um bom resultado de caso médio => QUICKSORT

Itens são extraídos de um universo denso => ​​SORTE DE CORTE

Desejo escrever o menor código possível => INSERTION SORT

timsort

O Timsort é “um mergesort adaptável, estável e natural” com ” desempenho sobrenatural em muitos tipos de matrizes parcialmente ordenadas (menos de lg (N!) Comparações necessárias, e tão pouco quanto N-1)”. A sorting interna do Python sort() usou esse algoritmo por algum tempo, aparentemente com bons resultados. Ele é especificamente projetado para detectar e aproveitar as subseqüências parcialmente classificadas na input, que geralmente ocorrem em conjuntos de dados reais. Geralmente é o caso no mundo real de que as comparações são muito mais caras do que trocar itens em uma lista, uma vez que normalmente apenas são trocados os pointers, o que muitas vezes faz do timsort uma excelente escolha. No entanto, se você souber que suas comparações são sempre muito baratas (por exemplo, ao escrever um programa de brinquedos para classificar números inteiros de 32 bits), existem outros algoritmos com probabilidade de melhor desempenho. A maneira mais fácil de aproveitar o timsort é, obviamente, usar o Python, mas como o Python é open source, talvez você também consiga emprestar o código. Como alternativa, a descrição acima contém detalhes mais do que suficientes para escrever sua própria implementação.

Tipo de inserção com o seguinte comportamento:

  1. Para cada elemento k nos slots 1..n , primeiro verifique se el[k] >= el[k-1] . Se sim, vá para o próximo elemento. (Obviamente pule o primeiro elemento.)
  2. Caso contrário, use a pesquisa binária nos elementos 1..k-1 para determinar o local de inserção e, em seguida, retire os elementos. (Você pode fazer isso somente se k>T onde T é algum valor limite; com pequeno k isso é um exagero).

Este método faz o menor número de comparações.

Tente classificar introspectivo. http://en.wikipedia.org/wiki/Introsort

É baseado em quicksort, mas evita o pior comportamento que o quicksort tem para listas quase ordenadas.

O truque é que esse algoritmo de sorting detecta os casos em que o quicksort entra no modo de pior caso e alterna para o tipo de pilha ou mesclagem. Partições quase ordenadas são detectadas por algum método de partição não-ingenuidade e pequenas partições são tratadas usando ordenação de inserção.

Você obtém o melhor de todos os principais algoritmos de sorting para o custo de mais código e complexidade. E você pode ter certeza de que nunca terá o pior desempenho, não importa como seus dados se pareçam.

Se você é um programador em C ++, verifique seu algoritmo std :: sort. Pode já usar internamente introspectivo.

O Splaysort é um obscuro método de sorting baseado em splay trees , um tipo de tree binária adaptativa. O Splaysort é bom não apenas para dados parcialmente ordenados, mas também para dados parcialmente ordenados por ordem inversa ou, na verdade, para quaisquer dados que possuam qualquer tipo de pedido pré-existente. É O (nlogn) no caso geral e O (n) no caso em que os dados são classificados de alguma forma (forward, reverse, organ-pipe, etc.).

Sua grande vantagem sobre o tipo de inserção é que ele não reverte para o comportamento O (n ^ 2) quando os dados não são classificados, portanto, você não precisa ter certeza absoluta de que os dados estão parcialmente classificados antes de usá-los. .

Sua desvantagem é a sobrecarga de espaço extra da estrutura de tree de reprodução necessária, bem como o tempo necessário para construir e destruir a tree de reprodução. Mas, dependendo do tamanho dos dados e da quantidade de pré-sorting esperada, a sobrecarga pode valer a pena pelo aumento da velocidade.

Um artigo sobre splaysort foi publicado em Software – Practice & Experience.

inserção ou tipo de shell!

O smoothsort de Dijkstra é um ótimo tipo de dados já classificados. É uma variante heapsort que é executada em O (n lg n) pior caso e O (n) melhor caso. Eu escrevi uma análise do algoritmo, caso você esteja curioso sobre como isso funciona.

O mergesort natural é outro realmente bom para isso – é uma variante mergesort de baixo para cima que funciona tratando a input como a concatenação de vários intervalos separados e, em seguida, usando o algoritmo de mesclagem para juntá-los. Você repete esse processo até que todo o intervalo de input seja classificado. Isso é executado no tempo O (n) se os dados já estiverem classificados e O (n lg n) no pior caso. É muito elegante, embora na prática não seja tão bom quanto outros tipos adaptativos como o Timsort ou o smoothsort.

A ordenação de inserção leva tempo O (n + o número de inversões).

Uma inversão é um par (i, j) tal que i < j && a[i] > a[j] . Ou seja, um par fora de ordem.

Uma medida de estar “quase ordenada” é o número de inversões – pode-se obter “dados quase ordenados” para significar dados com poucas inversões. Se alguém sabe que o número de inversões é linear (por exemplo, você acabou de acrescentar elementos O (1) a uma lista ordenada), a ordenação por inserção leva O (n) tempo.

Se os elementos já estiverem classificados ou houver apenas alguns elementos, seria um caso de uso perfeito para Insertion Sort!

Como todos os outros disseram, tome cuidado com Quicksort ingênuo – que pode ter o desempenho O (N ^ 2) em dados classificados ou quase ordenados. No entanto, com um algoritmo apropriado para escolha do pivô (random ou mediano de três), o Quicksort ainda funcionará bem.

Em geral, a dificuldade em escolher algoritmos, como inserir sorting, é decidir quando os dados estão suficientemente fora de ordem para que o Quicksort seja realmente mais rápido.

Não vou fingir ter todas as respostas aqui, porque acho que chegar às respostas reais pode exigir codificar os algoritmos e criá-los com base em amostras de dados representativas. Mas estive pensando sobre essa questão a noite toda, e aqui está o que me ocorreu até agora, e algumas suposições sobre o que funciona melhor onde.

Seja N o número total de itens, M seja o número fora de ordem.

Bubble sort terá que fazer algo como 2 * M + 1 passa por todos os N itens. Se M é muito pequeno (0, 1, 2?), Acho que isso será muito difícil de bater.

Se M for pequeno (digamos, menor que log N), o tipo de inserção terá um ótimo desempenho médio. No entanto, a menos que haja um truque que eu não esteja vendo, ele terá um pior desempenho no pior caso. (Certo? Se o último item da ordem vem em primeiro lugar, então você tem que inserir cada item, até onde eu posso ver, que vai matar o desempenho.) Eu estou supondo que há um algoritmo de sorting mais confiável lá fora para este caso, mas eu não sei o que é.

Se M é maior (digamos igual ou maior que log N), a sorting introspectiva é quase certamente a melhor.

Exceção a tudo isso: se você realmente sabe antecipadamente quais elementos não são classificados, sua melhor opção será extrair esses itens, classificá-los usando a sorting introspectiva e mesclar as duas listas classificadas em uma lista classificada. Se você pudesse descobrir rapidamente quais itens estão fora de ordem, essa também seria uma boa solução geral – mas não consegui descobrir uma maneira simples de fazer isso.

Pensamentos adicionais (durante a noite): Se M + 1

Outra interpretação da questão é que pode haver muitos itens fora de ordem, mas eles estão muito próximos de onde deveriam estar na lista. (Imagine começar com uma lista ordenada e trocar todos os outros itens pelo que vem depois dela.) Nesse caso, acho que o bubble sort funciona muito bem – acho que o número de passes será proporcional ao mais distante do que um item é. A ordenação por inserção funcionará mal, porque cada item fora de ordem acionará uma inserção. Eu suspeito que tipo introspectivo ou algo parecido funcionará bem também.

Se você precisar de implementação específica para classificar algoritmos, estruturas de dados ou qualquer coisa que possua um link para o acima, eu poderia recomendar o excelente projeto “Estruturas de Dados e Algoritmos” no CodePlex?

Ele terá tudo que você precisa sem reinventar a roda.

Apenas meu pequeno grão de sal.

Esta bela coleção de algoritmos de ordenação para este propósito nas respostas, parece não ter o Gnome Sort , que também seria adequado, e provavelmente requer o menor esforço de implementação.

A ordenação de inserção é o melhor caso O (n) na input classificada. E é muito perto de input principalmente classificada (melhor do que a sorting rápida).

pondere tente a pilha. Eu acredito que é o mais consistente dos tipos O (ng n n).

Bubble-sort (ou, ainda mais seguro, o bubble sort bidirecional) é provavelmente ideal para listas ordenadas, embora eu aposto que um comb-sort modificado (com um tamanho inicial muito menor) seria um pouco mais rápido quando a lista não fosse Não tão perfeitamente ordenada. Comb sort degrada para bubble-sort.

bem, depende do caso de uso. Se você souber quais elementos são alterados, remover e inserir será o melhor caso, tanto quanto eu estou preocupado.

Tipo de bolha é definitivamente o vencedor O próximo no radar seria tipo de inserção.

Mantenha-se longe do QuickSort – é muito ineficiente para dados pré-classificados. O tipo de inserção manipula bem dados quase ordenados, movendo o menor número de valores possível.