insert sort

Algoritmo insert sortionO Insertion sort é um algoritmo que faz a ordenação de um vetor de numeros, . Neste algoritmo o vetor é percorrido da esquerda para a direita, à medida que vai avançando vai deixando os elementos que estão a esquerda ordenados, sua complexidade no pior caso é de O (n² , e no melhor caso (quando já estão ordenados é de O(n vantagens : facil implementação , é um algoritmo estavel, o vetor já ordenado favorece a ordenação desvantagens: numero grande de movimentações , ordem de compexidade quadratica, ineficiente quando o vetor esta ordenado iversamente. ( pior caso )
Insertion Sort com Busca Binária
Este algoritmo funciona de maneira semelhante ao Insertion Sort normal, porém tenta diminuir o número de comparações utilizadas para achar o local de inserção do elemento no vetor ordenado. O artifício usado é uma busca binária sobre a o vetor já ordenado, dessa maneira serão sempre feitas log n comparações para encontrar o lugar do elemento a ser inserido. Esta "otimização" não diminui o custo assintótico do algoritmo, já que após achar o lugar correto para a inserção, ainda é preciso fazer o mesmo número de deslocamentos que o caso anterior. O custo do pior caso desse Inserition Sort continua sendo O(n^2), embora multiplicado por uma constante menor (como pode ser observado no gráfico ao final do relatório), porém para o melhor caso ele tem uma complexidade de Ω(log(n!)), ou seja, ele no melhor caso perde do Insertion Sort original.
Insertion sortO 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.

Figura 4: Esquema de funcionamento do Insertion SortNeste passo é verificado se o 5 é menor que o 3, como essa condição é falsa, então não há troca.
É