Baixe o app para aproveitar ainda mais
Prévia do material em texto
Prof. Aleffer Rocha É o método de ordenação favorito entre os jogadores de cartas. Em cada passo, a partir de 𝑖 = 1, para um vetor de 0 a 𝑛 − 1 o 𝑖-ésimo item da sequência fonte é apanhado e transferido para a sequência destino, sendo inserido no seu lugar apropriado. 1 20 3 4 5v[6] = 34 13 51 0 78 14 1 20 3 4 5 34 13 51 0 78 14 v[6] = NÃO ORDENADOORDENADO aux 1 20 3 4 5 34 51 0 78 14 v[6] = NÃO ORDENADOORDENADO aux 13 1 20 3 4 5 34 51 0 78 14 v[6] = NÃO ORDENADOORDENADO aux 13 1 20 3 4 5 34 51 0 78 14 v[6] = NÃO ORDENADOORDENADO aux 13 1 20 3 4 5 34 51 0 78 14 v[6] = NÃO ORDENADOORDENADO aux 13 1 20 3 4 5 34 0 78 14 v[6] = NÃO ORDENADOORDENADO aux 13 51 1 20 3 4 5 34 51 0 78 14 v[6] = NÃO ORDENADOORDENADO aux 13 1 20 3 4 5 34 51 0 78 14 v[6] = NÃO ORDENADOORDENADO aux 13 1 20 3 4 5 34 51 78 14 v[6] = NÃO ORDENADOORDENADO aux 13 0 1 20 3 4 5 34 51 78 14 v[6] = NÃO ORDENADOORDENADO aux 13 0 1 20 3 4 5 34 51 78 14 v[6] = NÃO ORDENADOORDENADO aux 13 0 1 20 3 4 5 34 51 78 14 v[6] = NÃO ORDENADOORDENADO aux 13 0 1 20 3 4 5 34 51 78 14 v[6] = NÃO ORDENADOORDENADO aux 130 1 20 3 4 5 34 51 78 14 v[6] = NÃO ORDENADOORDENADO aux 130 1 20 3 4 5 34 51 14 v[6] = NÃO ORDENADOORDENADO aux 130 78 1 20 3 4 5 34 51 78 14 v[6] = NÃO ORDENADOORDENADO aux 130 1 20 3 4 5 34 51 78 14 v[6] = NÃO ORDENADOORDENADO aux 130 1 20 3 4 5 34 51 78 v[6] = NÃO ORDENADOORDENADO aux 130 14 1 20 3 4 5 34 51 78 v[6] = NÃO ORDENADOORDENADO 130 aux 14 1 20 3 4 5 34 51 78 v[6] = NÃO ORDENADOORDENADO 130 aux 14 1 20 3 4 5 34 51 78 v[6] = NÃO ORDENADOORDENADO 130 aux 14 1 20 3 4 5 34 51 78 v[6] = 130 14 1 20 3 4 5v[6] = 34 13 51 0 78 14 1 20 3 4 5v[6] = 1 20 3 4 5v[6] = 1 20 3 4 5v[6] = 51 0 78 1413 34 140 13 785134 7851340 13 14 Início InsertionSort(v[], ini, fim) Para i de ini + 1 até fim faça aux = v[i]; j = i – 1; Enquanto j >= ini e aux < v[j] faça Troca(v[j+1], v[j]); j = j – 1; Fim Enquanto Fim Para Fim InsertionSort Qual a ordem de grandeza no pior caso do algoritmo Insertion Sort? 𝑂(𝑛2) onde 𝑛 é a quantidade de elementos no vetor. • ZIVIANI, Nivio et al. Projeto de algoritmos: com implementações em Pascal e C. Thomson, 2004. ESTRUTURA DE DADOS 1 INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT INSERTION SORT MATERIAL UTILIZADO
Compartilhar