Análise Comparativa de Algoritmos de Ordenação em C e Golang: Estudo de Desempenho com Dados Reais

Implementálos nas duas linguagens utilizadas na disciplina C e Golang 4 Para cada implementação deverão ser realizados os seguintes testes exaustivos utilizando os arquivos numerostxt nomestxt e pessoatxt os quais são fornecidos com esta tarefa da seguinte forma a Para cada arquivo devem ser realizados testes de desempenho começando com 1000 registros de dados extraídos dos arquivos supramencionados e aumentando o número de registros de 1000 em 1000 a cada execução até alcançar o número máximo de registros nos arquivos 100000 registros Caso algum algoritmo não suporte um volume de dados tão grande executar até o volume máximo suportado pelo algoritmo e relatar a ocorrência b O arquivo pessoatxt é composto por dois campos código e pessoa devendo ser ordenado por ambos os campos por código 1ª chave e por nome 2ª chave c Os tempos de execução número de trocas e número de comparações devem ser coletados para cada execução de cada arquivo d Ao final devese apresentar um estudo comparativo sobre os algoritmos escolhidos com tabelas comparativas e gráficos de desempenho para todos os dados coletados comparando os dois algoritmos em ambas as implementações e com cada um dos arquivos de teste e Devem ser comparados o número de comparações o número de trocas e o tempo de execução de cada algoritmo A plataforma computacional utilizada para a execução dos testes deve ser a mesma para que não haja influência da plataforma nos resultados obtidos Esta plataforma deverá estar descrita no relatório 5 Deve ser entregue a Um relatório contendo as análises organizado da seguinte forma i Introdução deve conter uma descrição sucinta do problema de ordenação e dos algoritmos escolhidos para a realização do experimento max 1 página ii Metodologia deve descrever como o experimento foi realizado 1 Qual plataforma computacional utilizada hardware Sistema Operacional Linguagens de programação 2 Como os testes foram realizados apresentar aqui os gráficos tamanho X trocas tamanho X comparações tamanho X tempo e tabelas comparativas iii Conclusões deve apresentar as conclusões obtidas a partir do experimento 1 Qual a melhor implementação de cada algoritmo CGo para cada tipo de dados 2 Qual o melhor algoritmo para cada tipo de dados considerando apenas uma das linguagens 3 Qual algoritmo foi melhor para cada tipo de dados independente da linguagem de implementação 4 Qual linguagem apresentou melhor desempenho geral independente do algoritmo implementado 5 Qual algoritmo apresentou melhor desempenho geral independente da linguagem de implementação 1 Introdução A ordenação é um problema central em Ciência da Computação e tem sido objeto de extenso estudo devido à sua importância prática e teórica A tarefa de classificação envolve a disposição de um conjunto de itens em uma ordem particular crescente ou decrescente com base em algum critério Este problema se manifesta em diversas aplicações desde a organização de dados em um banco de dados até a renderização de elementos gráficos em uma tela Além disso a eficiência da ordenação pode ter impacto direto no desempenho de outros algoritmos e sistemas que dependem de dados ordenados Neste estudo escolhemos dois algoritmos de classificação populares e amplamente utilizados o Bubble Sort e o Insertion Sort para um conjunto de experimentos de desempenho O Bubble Sort é um algoritmo de ordenação simples que funciona trocando repetidamente elementos adjacentes se estiverem na ordem errada Apesar de sua simplicidade o Bubble Sort não é comumente usado para grandes conjuntos de dados devido à sua alta complexidade temporal O Insertion Sort por outro lado é um algoritmo de classificação mais eficiente que constrói a saída final um item por vez É muito mais eficiente que outros algoritmos de ordenação quadrática simples como o Bubble Sort especialmente para listas pequenas e principalmente ordenadas Os algoritmos foram implementados em duas linguagens de programação diferentes C e Go C é uma linguagem de programação de propósito geral que oferece recursos de baixo nível e alto nível enquanto Go é uma linguagem de programação de código aberto que é eficiente expressiva e fácil de ler e escrever Os experimentos foram projetados para avaliar o desempenho dos algoritmos de ordenação implemen tados em termos de tempo de execução número de comparações e número de trocas com um número crescente de entradas Os dados para os experimentos foram extraídos de três arquivos diferentes cada um contendo diferentes tipos de dados números nomes e registros de pessoas Este relatório apresenta uma descrição detalhada dos experimentos a metodologia usada os resultados obtidos e uma discussão dos resultados Esperase que os resultados deste estudo ofereçam insights úteis sobre o comportamento e o desempenho desses algoritmos de classificação em diferentes contextos 2 Metodologia 21 Plataforma Operacional Foi utilizado um computador com sistema operacional Windows 10 com 32 GB de memória Ram e processador intel i5 Foram utilizadas as linguagens de programação C e Go 22 Resultados e Discussões Vamos agora apresentar os gráficos tamanho x tempo tamanho x comparações e tamanho x trocas para todos os 3 tipos de arquivo e 2 tipos de ordenação É importante destacar que o tamanho está dividido por 1000 no gráfico para facilitar a visualização e que o tempo está em milisegundos Além disso foram realizados testes com até 50000 itens dos arquivos de dados começandose com 1000 itens e aumentando de 1000 em 1000 Não foi possível realizar os testes indo de 1000 em 1000 até 100000 pois os testes levariam muito tempo Apenas o bubble sort e insertion sort de numeros em c levou aproximadamente uma hora Logo a estimativa para rodar todos os testes seria de cerca de 6h Fazendo com 50000 itens o trabalho todo rodou em menos de uma hora 221 C Para o arquivo de numeros obtivemos os seguintes gráficos 1 Buble Sort tamanho x tempo Figura 1 Buble Sort tamanho x tempo Buble Sort tamanho x comparações Figura 2 Buble Sort tamanho x comparações Buble Sort tamanho x trocas 2 Figura 3 Buble Sort tamanho x trocas Insetion Sort tamanho x tempo Figura 4 Insetion Sort tamanho x tempo Insetion Sort tamanho x comparações 3 Figura 5 Insetion Sort tamanho x comparações Insetion Sort tamanho x trocas Figura 6 Insetion Sort tamanho x trocas Para o arquivo de nomes obtivemos os seguintes gráficos Buble Sort tamanho x tempo 4 Figura 7 Buble Sort tamanho x tempo Buble Sort tamanho x comparações Figura 8 Buble Sort tamanho x comparações Buble Sort tamanho x trocas 5 Figura 9 Buble Sort tamanho x trocas Insetion Sort tamanho x tempo Figura 10 Insetion Sort tamanho x tempo Insetion Sort tamanho x comparações 6 Figura 11 Insetion Sort tamanho x comparações Insetion Sort tamanho x trocas Figura 12 Insetion Sort tamanho x trocas Para o arquivo de pessoas obtivemos os seguintes gráficos Bubble Sort tamanho x tempo 7 Figura 13 Buble Sort tamanho x tempo Bubble Sort tamanho x comparações Figura 14 Buble Sort tamanho x comparações Bubble Sort tamanho x trocas 8 Figura 15 Buble Sort tamanho x trocas Insetion Sort tamanho x tempo Figura 16 Insetion Sort tamanho x tempo Insetion Sort tamanho x comparações 9 Figura 17 Insetion Sort tamanho x comparações Insetion Sort tamanho x trocas Figura 18 Insetion Sort tamanho x trocas 222 GO Para o arquivo de numeros obtivemos os seguintes gráficos Buble Sort tamanho x tempo 10 Figura 19 Buble Sort tamanho x tempo Buble Sort tamanho x comparações Figura 20 Buble Sort tamanho x comparações Buble Sort tamanho x trocas 11 Figura 21 Buble Sort tamanho x trocas Insetion Sort tamanho x tempo Figura 22 Insetion Sort tamanho x tempo Insetion Sort tamanho x comparações 12 Figura 23 Insetion Sort tamanho x comparações Insetion Sort tamanho x trocas Figura 24 Insetion Sort tamanho x trocas Para o arquivo de nomes obtivemos os seguintes gráficos Buble Sort tamanho x tempo 13 Figura 25 Buble Sort tamanho x tempo Buble Sort tamanho x comparações Figura 26 Buble Sort tamanho x comparações Buble Sort tamanho x trocas 14 Figura 27 Buble Sort tamanho x trocas Insetion Sort tamanho x tempo Figura 28 Insetion Sort tamanho x tempo Insetion Sort tamanho x comparações 15 Figura 29 Insetion Sort tamanho x comparações Insetion Sort tamanho x trocas Figura 30 Insetion Sort tamanho x trocas Para o arquivo de pessoas obtivemos os seguintes gráficos Buble Sort tamanho x tempo 16 Figura 31 Buble Sort tamanho x tempo Buble Sort tamanho x comparações Figura 32 Buble Sort tamanho x comparações Buble Sort tamanho x trocas 17 Figura 33 Buble Sort tamanho x trocas Insetion Sort tamanho x tempo Figura 34 Insetion Sort tamanho x tempo Insetion Sort tamanho x comparações 18 Figura 35 Insetion Sort tamanho x comparações Insetion Sort tamanho x trocas Figura 36 Insetion Sort tamanho x trocas 3 Conclusão Vamos responder agora as perguntas finais de análise 1 A implementação em Go performou melhor do que a de C 2 Go performou melhor em todos os tipos de arquivos 3 Insertion Sort foi melhor para todos os tipos de dados 4 Go performou melhor independentemente do tipo de algoritmo 5 Insertion sort apresentou o melhor desempenho geral 19