Ordenação AED I

Abstract. This report is about the relationship between sorting algorithms, showing the time, the number of iterations and comparisons of the best known sorting algorithms.

Resumo. Este relat´orio e´ sobre a relac¸a˜ o entre os algoritmos de ordenac¸a˜ o, mostrando o tempo, o n´umero de comparac¸o˜ es e iterac¸o˜ es dos algoritmos mais conhecidos da ordenac¸a˜ o.

1. Introduc¸a˜ o
A proposta de realizac¸a˜ o deste trabalho e´ a an´alise e comparac¸a˜ o de tempo, n´umero de iterac¸o˜ es e comparac¸o˜ es entre 11 algoritmos de ordenac¸a˜ o: BubbleSort, SelectionSort,
InsertionSort, ShellSort, HeapSort, o IntroSort (H´ıbrido do QuickSort e InsertionSort) e mais cinco tipos diferentes de QuickSort, alternando a forma de como o elemento pivˆo e´ escolhido: Pivˆo primeiro elemento, pivˆo u´ ltimo elemento, pivˆo mediana, pivˆo randˆomico e pivˆo meio.

2. Implementac¸a˜ o
2.1. Descric¸a˜ o sobre as decis˜oes de projeto e implementac¸a˜ o do programa
A implementac¸a˜ o foi feita em dupla, nenhum dos integrantes ficou respons´avel por uma parte espec´ıfica, ambos usaram a combinac¸a˜ o Pages (ferramenta de edic¸a˜ o de texto, com opc¸a˜ o de m´ultiplos editores em tempo real na nuvem) + Skype para codificarmos o algoritmo.
2.2. Descric¸a˜ o das estruturas de dados usadas no programa
Optamos pela utilizac¸a˜ o de um vetor dinˆamico para as massas de entrada, evitando que v´arios vetores fossem alocados na mem´oria. No corpo principal do algoritmo utilizamos um case, o usu´ario do programa escolhe a massa de entrada atrav´es dele e quando escolhido, um for de 1 a 100 ir´a chamar as respectivas func¸o˜ es dos 11 algoritmos de ordenac¸a˜ o 100 vezes, retornando o tempo m´edio e n´umero de iterac¸o˜ es m´edias de cada tipo de ordenac¸a˜ o.
2.3. Funcionamento das principais func¸o˜ es e procedimentos utilizados
Utilizamos as func¸o˜ es de tempo j´a implementadas pelo professor M´ario e pelo aluno
S´avio Cardoso.
Basicamente a maioria das func¸o˜ es