Trabalho de PA

Abstract. This paper analyzes the complexity of various sorting algorithms. A vector of the same size and same values were used as input in the implementation of each algorithm. Lists the input values used, runtime and standard deviation obtained with each method of ordering. The times obtained are represented graphically for better understanding the performance differences between the algorithms.
Resumo. Este trabalho analisa a complexidade de diversos algoritimos de ordenação. Um vetor de mesmo tamanho e mesmos valores foi utilizado como entrada na execução de cada algoritmo. São apresentados os valores de entrada utilizados, tempo de execução e desvio padrão obtidos com cada um dos métodos de ordenação. Os tempos obtidos são representados graficamente para melhor percepção das diferenças de desempenho entre os algoritmos.
1. Introdução
A complexidade dos algoritmos depende do tamanho e dos valores de entrada [Parreira Júnior, 2014]. Para entradas de mesmo tamanho o tempo de execução pode variar, é necessário escolher qual a entrada entre todos do mesmo tamanho será usada para antes de avaliar a complexidade do algoritmo. Para que um algoritmo de ordenação seja estável, ele precisa manter a ordem relativa dos registros iguais. O algoritmo de Inserção, por exemplo, se comporta melhor do que os demais quando o vetor está semi-ordenado ou ordenado, já o Quicksort, Seleção, Shellsort e Heapsort, são instáveis, pois não mantém a ordem para os elementos iguais, trocando as posições destes elementos. Para entradas pequenas os algoritmos de ordenação de complexidade quadrática como o Seleção, Bolha e Inserção, são mais eficientes que os algoritmos com complexidade de O(nlogn), como o Quicksort.
Tabela 1. Complexidade dos algoritmos
2. Análise
Neste trabalho foi implementado e analisado os algoritmos de ordenação: bolha, seleção, inserção, heapsort, mergesort, quicksort. Para analise dos algoritmos foram gerados