Insertion sort
O Insertion sort é um algoritmo simples e eficiente quando aplicado em pequenas listas. Neste algoritmo a lista é percorrida da esquerda para a direita, à medida que avança vai deixando os elementos mais à esquerda ordenados.
O algoritmo funciona da mesma forma que as pessoas usam para ordenar cartas em um jogo de baralho como o pôquer.
Esquema de funcionamento do Insertion Sort:
- Neste passo é verificado se o 5 é menor que o 3, como essa condição é falsa, então não há troca.
- É verificado se o quatro é menor que o 5 e o 3, ele só é menor que o 5, então os dois trocam de posição.
- É verificado se o 2 é menor que o 5, 4 e o 3, como ele é menor que 3, então o 5 passa a ocupar a posição do 2, o 4 ocupa a posição do 5 e o 3 ocupa a posição do 4, assim a posição do 3 fica vazia e o 2 passa para essa posição.
O mesmo processo de comparação acontece com o número 1, após esse processo o vetor fica ordenado.
Pseudocódigo
Animações
Fontes: http://pt.wikipedia.org/wiki/Insertion_sort;
Youtube;
Devmedia.
Qual o melhor caso e pior caso do Insertion sort (em termos de complexidade) ?
ResponderExcluirCara depende do ponto de vista que vc vai adotar, vc se refere a complexidade de algoritmo ou complexidade em termos de uso ou em termo de aplicação?
Excluirnaturalmente o melhor caso para um algoritmo de ordenação é quando o a estrutura já se encontra ordenada, no pior caso vai depender do tipo de dados usado e tb do número de elementos que o array contem como é dito no enunciado é um algoritmo bacana para pequenos vetores.
Yvo, o melhor caso está em ordem linear de processamento, com estudos bem otimistas. Já o pior caso é complexidade polinomial de grau 2, isso com testes forçando bastante a sua capacidade de processamento, ou seja, em termos mais leigos, esse algoritmo de ordenação dá muito bem conta do recado quando é necessário. Em particular, esse é um dos que eu acho melhores e mais simples de trabalhar.
Excluir