Trabalho1 EDA Jo oVictor PedroYago PedroIvo ClauberMartins

Complexidade e Ordenação: Selection Sort e Heap Sort
João Victor P. Soares
1309108

Pedro Ivo D. Loiola
12092019

Pedro Yago R. de Sousa
1309124

Clauber Martins

Resumo
Este artigo apresenta a análise da complexidade e a execução de algoritmos de ordenação do tipo Selection Sort e Heap Sort.
Palavras-Chave: SelectionSort; HeapSort;, Complexidade; Ordenação;

Abstract
This article presents the analysis of the complexity and execution algorithms sorting type SelectionSort and HeapSort.
Keywords: SelectionSort; HeapSort; Complexity; Sort;

1 Selection Sort
O Selection Sort é um método de ordenação que se baseia em em escolher o menor valor da chave de um vetor e trocá-lo com o primeiro registro da sequência. Este processo é repetido trocando o menor valor da chave dos n-1 registros (descontando o primeiro registros) com o segundo registro, troca-se o menor valor da chave n-2 (descontando o primeiro e o segundo registros)

1.2 Ordenação
Para ordenar os números a partir de um arquivo txt e exibir os resultados necessários (pior caso e melhor caso), foi necessário modificar o algoritmo do Selection Sort para que ele executasse o melhor caso e o pior caso. A seguir é possível ver os códigos de cada caso

Melhor Caso void melhor_caso_select(int *f){ int *vetor, c, i = 0, d, posicao, troca, teste = 0; arq_o = fopen("original.txt", "r"); arq_c = fopen("select_pior.txt", "w"); vetor = (int*)malloc(melhor_caso*sizeof(int)); for (c = 0; c < melhor_caso; c++){ //ler dados do arquivo original fscanf(arq_o, "%d", &vetor[c]); } //Função... inicio = clock(); for (c = 0; c < (melhor_caso - 1); c++){ posicao = c; for (d = c + 1; d < melhor_caso; d++){ if (vetor[posicao] > vetor[d]) posicao = d; } if (posicao != c){ troca = vetor[c]; vetor[c] = vetor[posicao]; vetor[posicao] = troca; } }

//Fim... fim = clock(); printf("\n\n"); printf("Tempo %f segundos totais\n", (fim - inicio) / (float)CLOCKS_PER_SEC);