O Algoritmos de Ordenação
Por: Beatriz Gabriela • 5/3/2019 • Trabalho acadêmico • 7.064 Palavras (29 Páginas) • 145 Visualizações
RESUMO
O trabalho a ser abordado tem como ênfase o desenvolvimento de um programa em linguagem C com geração de dados aleatórios para ordenação através de algoritmos, de variados tamanhos para estudo e análise de complexidade dos resultados gerados pelo desempenho das técnicas de ordenação.
Palavras Chave: análise, linguagem de programação, linguagem C, algoritmos de ordenação, dados, complexidade, performance.
LISTA DE FIGURAS
Figura 1 – Vetor inicial Inserção Direta 8
Figura 2 - Definição de Chave para Inserção Direta 9
Figura 3 – Chave percorrendo o vetor Inserção Direta 9
Figura 4 - Segunda passada no vetor Inserção Direta 10
Figura 5 - Terceira passada no vetor Inserção Direta 10
Figura 6 - Quarta passada no vetor Inserção Direta 11
Figura 7 - Posicionamento da Chave Inserção Direta 11
Figura 8 - Vetor ordenado pela Inserção Direta 11
Figura 9 - Vetor inicial BubbleSort 13
Figura 10 - Primeira comparação do BubbleSort 13
Figura 11 - Segunda comparação do BubbleSort 13
Figura 12 - Terceira comparação do BubbleSort 13
Figura 13 - Quarta comparação do BubbleSort 13
Figura 14 - Reinicio da comparação BubbleSort 14
Figura 15 - Troca de elemento e finalização BubbleSort 14
Figura 16 - Vetor ordenado BubbleSort 14
Figura 17 - Comparação em relação ao primeiro elemento Seleção Direta 16
Figura 18 - Comparação em relação ao segundo elemento Seleção Direta 16
Figura 19 - Comparação em relação ao terceiro elemento Seleção Direta 17
Figura 20 - Comparação em relação ao quarto elemento Seleção Direta 17
Figura 21 - Comparação em relação ao quinto elemento Seleção Direta 17
Figura 22 - Inicio da varredura ShakeSort 18
Figura 23 - Volta da varredura do ShakeSort 18
Figura 24 - Verificação pra término da ordenação ShakeSort 19
Figura 25 - Vetor ordenado ShakeSort 19
Figura 26 - Vetor inicial QuickSort 20
Figura 27 - Definição das variáveis auxiliares do método QuickSort 20
Figura 28 - Movimentação do auxiliar I QuickSort 21
Figura 29 - Mudança de auxiliares QuickSort 21
Figura 30 - Troca de valores dos auxiliares QuickSort 21
Figura 31 - Segunda mudança de auxiliares QuickSort 22
Figura 32 - Segunda troca de valores dos auxiliares QuickSort 22
Figura 33 - Encontro dos auxiliares QuickSort 22
Figura 34 - Terceira troca de valores dos auxiliares QuickSort 22
Figura 35 - Posicionamento do pivô QuickSort 23
Figura 36 - Posição e ordenação do pivô QuickSort 23
Figura 37 - Divisão do vetor QuickSort 23
Figura 38 - Recomeço do encontro do pivô da sublista amarela QuickSort 24
Figura 39 - Recursividade dos passos do método QuickSort 24
Figura 40 - Subdivisão do vetor QuickSort 24
Figura 41 – Nova regra para os auxiliares QuickSort 25
Figura 42 - Troca do pivô com o valor dos auxiliares QuickSort 25
Figura 43 - Sublista unitária QuickSort 25
Figura 44 - Ordenação final da primeira sublista QuickSort 25
Figura 45 - Divisão em sublistas QuickSort 26
Figura 46 - Recursão da ordenação e finalização da ordenação QuickSort 27
Figura 47 - Divisão do vetor MergeSort 28
Figura 48 - Junção do vetor MergeSort 28
Figura 49 - Posição dos elementos em árvore HeapSort 30
Figura 50 - Max-heap do vetor HeapSort 31
Figura 51 - Troca da raíz HeapSort 32
Figura 52 - Segunda troca de raíz HeapSort 32
Figura 53 - Terceira troca de raíz HeapSort 33
Figura 54 - Quarta troca de raíz HeapSort 34
Figura 55 - Quinta troca de raíz HeapSort 35
Figura 56 - Vetor ordenado HeapSort 35
Figura 57 - Resultados do desempenho dos algoritmos de ordenação 37
Figura 58 - Resultado do desempenho dos algoritmos de complexidade N² 38
Figura 59 - Resultado do desempenho dos algoritmos de complexidade N log N 39
SUMÁRIO
INTRODUÇÃO 6
1. ALGORITMOS DE ORDENAÇÃO 8
1.1. INSERÇÃO DIRETA 8
1.1.1. FUNCIONAMENTO/EXEMPLO 8
1.2. BUBBLESORT 11
1.2.1. FUNCIONAMENTO/EXEMPLO 12
...