O Algoritmos de Ordenação

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

...