Há sempre um bom motivo para usar o Insertion Sort?

Para a sorting de propósito geral, a resposta parece ser não, pois a sorting rápida, a mesclagem e o tipo de heap tendem a ter um melhor desempenho nos cenários de média e pior. No entanto, a ordenação de inserção parece se destacar na sorting incremental, ou seja, adicionar elementos a uma lista de cada vez durante um período prolongado, mantendo a lista classificada, especialmente se a sorting de inserção for implementada como uma linked list (O n) caso médio vs. O (n)). No entanto, um heap parece ser capaz de executar apenas (ou quase) também para ordenação incremental (adicionar ou remover um único elemento de um heap tem o pior cenário de O (log n)). Então, o que exatamente o tipo de inserção tem a oferecer sobre outros algoritmos de sorting baseados em comparação ou heaps?

De http://www.sorting-algorithms.com/insertion-sort :

Embora seja um dos algoritmos de ordenação elementares com O (n 2 ) pior momento, a ordenação de 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.

Um conceito importante na análise de algoritmos é a análise assintótica . No caso de dois algoritmos com diferentes tempos de execução assintóticos, como um O (n ^ 2) e um O (nlogn), como é o caso da inserção e quicksort, respectivamente, não é definitivo que um seja mais rápido que o outro.

A distinção importante com esse tipo de análise é que, para um N suficientemente grande , um algoritmo será mais rápido que o outro. Ao analisar um algoritmo até um termo como O (nlogn), você solta constantes. Ao analisar de maneira realista a execução de um algoritmo, essas constantes serão importantes apenas para situações de pequeno n.

Então o que isso quer dizer? Isso significa que, para alguns n pequenos, alguns algoritmos são mais rápidos. Este artigo do EmbeddedGurus.net inclui uma perspectiva interessante sobre a escolha de diferentes algoritmos de ordenação no caso de um espaço limitado (16k) e sistema de memory limitada. Obviamente, o artigo referencia apenas a sorting de uma lista de 20 inteiros, portanto ordens maiores de n são irrelevantes. Código mais curto e menos consumo de memory (além de evitar a recursion) eram decisões mais importantes.

A ordenação de inserção tem pouca sobrecarga, pode ser escrita de forma bastante sucinta e tem vários benefícios principais: é estável e tem um caso de execução bastante rápido quando a input está quase classificada.

Sim, há um motivo para usar uma sorting de inserção ou uma de suas variantes.

As alternativas de ordenação (quick sort, etc.) das outras respostas aqui fazem a suposição de que os dados já estão na memory e prontos para serem usados.

Mas se você está tentando ler uma grande quantidade de dados de uma fonte externa mais lenta (digamos, um disco rígido), há uma grande quantidade de tempo desperdiçado, pois o gargalo é claramente o canal de dados ou a própria unidade. Ele simplesmente não consegue acompanhar a CPU. Uma série natural de espera ocorre durante qualquer leitura. Essas esperas são desperdiçadas ciclos de CPU, a menos que você os use para classificar conforme você for .

Por exemplo, se você fizer a sua solução para isso, faça o seguinte:

  1. Leia uma tonelada de dados em um loop dedicado na memory
  2. Ordenar esses dados

Você provavelmente levaria mais tempo do que se fizesse o seguinte em dois tópicos.

Tópico A:

  1. Leia um dado
  2. Coloque o dado na fila FIFO
  3. (Repita até que os dados esgotados da unidade)

Tópico B:

  1. Obter um dado da fila FIFO
  2. Insira-o no lugar adequado na sua lista classificada
  3. (repita até a fila vazia E o segmento A diz “concluído”).

… o acima permitirá que você use o tempo perdido. Nota: O encadeamento B não impede o progresso do encadeamento A.

No momento em que os dados forem lidos na íntegra, eles estarão classificados e prontos para uso.

A maioria dos procedimentos de sorting usará quicksort e, em seguida, inserção de sorting para conjuntos de dados muito pequenos.

Se você está falando sobre manter uma lista ordenada, não há vantagem sobre algum tipo de tree, é apenas mais lento.

Bem, talvez consuma menos memory ou seja uma implementação mais simples.

Inserir em uma lista classificada envolverá uma varredura, o que significa que cada inserção é O (n), portanto, ordenar n itens se torna O (n ^ 2)

Inserindo em um container como uma tree balanceada, normalmente é log (n), portanto a ordenação é O (n log (n)) que é melhor.

Mas para listas pequenas, dificilmente faz alguma diferença. Você pode usar uma sorting de inserção se tiver que escrevê-la você mesmo sem nenhuma biblioteca, as listas são pequenas e / ou você não se importa com o desempenho.

SIM,

A ordenação por inserção é melhor que a Classificação Rápida em listas curtas.

Na verdade, uma sorting rápida ideal tem um limite de tamanho no qual ela é interrompida e, em seguida, toda a matriz é classificada por meio da inserção em relação aos limites.

Além disso…

Para manter um placar, o Binary Insertion Sort pode ser o melhor possível.

Veja esta página .

Para sorting de inserção de matrizes pequenas, ela é executada com mais rapidez que o quicksort. Java 7 e Java 8 usam quicksort de pivot duplo para ordenar tipos de dados primitivos. O desvio rápido do pivô duplo executa o quicksort típico de pivô único. De acordo com o algoritmo de quicksort de pivot duplo:

  1. Para matrizes pequenas (comprimento <27), use o algoritmo de classificação Insertion.
  2. Escolha dois pivôs ………..

Definitivamente, a ordenação por inserção executa quicksort para matrizes pequenas e é por isso que você está mudando para a ordenação de inserção para matrizes de comprimento menor que 27 . A razão pode ser que não há recursões no tipo de inserção.

Fonte: http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf