Este artigo é parte da série sobre algoritmos de ordenação em JavaScript. Você pode encontrar o resto da série aqui. Se você é novo em algoritmos de classificação, ou algoritmos em geral, leia isso primeiro para obter uma base sólida para avançar. Hoje vou cobrir os prós e contras do tipo de inserção. O tipo de inserção é mais complexo, mas um pouco mais útil do que o tipo de bolha. O pior cenário para isso é semelhante ao bubble sort, mas o melhor caso o torna adequado para momentos em que você tem certeza de que uma lista quase classificada ou provavelmente já classificada. Vamos ao quadro geral.
a classificação de inserção funciona observando cada elemento dentro de uma lista (começando com o segundo elemento) e comparando-o com o item anterior. Se o item anterior for maior, eles serão trocados. Isso continua até que o item seja menor, momento em que fazemos o mesmo para o próximo elemento da lista.
a classificação de inserção não é tão ruim assim.. contanto que você o use nas circunstâncias certas.
- é mais rápido do que a maioria dos algoritmos de classificação O(n log n) para pequenas listas.
- é extremamente eficiente em termos de memória, exigindo apenas o(1) espaço auxiliar para o único item que está sendo movido.
- é estável-elementos iguais aparecem na mesma ordem na lista classificada.
- é adaptável – é rápido ao classificar listas classificadas principalmente ou ao adicionar itens a uma lista já classificada.
- é muito fácil de implementar!
complexidade
a complexidade temporal deste algoritmo, na pior das hipóteses, é quadrática-o (n2). À medida que n se aproxima do infinito, o caso médio se aproxima do pior caso dividido por dois. No entanto, como se sua lista estiver classificada ou quase assim, ela pode ser O(n) na melhor das hipóteses e, portanto, bem adaptada a esse cenário.
quando é rápido
como mencionado acima, pode ser rápido em certas circunstâncias. Considere a matriz, ao usar um algoritmo como merge sort, ainda precisaríamos dividir todos os itens e depois mesclá-los de volta. Com a classificação de inserção, só precisamos verificar se estão na ordem correta ‘classificada até agora’, então mudamos todos eles para um índice para 1.
como a classificação de inserção é uma classificação adaptativa, ela também a torna um ‘algoritmo online’, O que significa que podemos começar a classificar antes de obter todos os itens e mesclar as listas assim que a classificação parcial for concluída.
Pseudocódigo
function insertionSort(array)
Loop through array
Create temp var for current element
Create var and set equal to previous element's index
Loop backwards while index >= 0 and current element > temp var
Set next element equal to current element
Set next element equal to temp
Código
o Próximo? Mesclar classificação. Um dos algoritmos de classificação mais usados nos navegadores hoje.
