Relatório Estrutura de Dados

GOVERNO DO ESTADO DE MATO GROSSO SECRETARIA DE CIÊNCIA E TECNOLOGIA UNIVERSIDADE DO ESTADO DE MATO GROSSO CAMPUS UNIVERSITÁRIO DE ALTO ARAGUAIA DEPARTAMENTO DE COMPUTAÇÃO Disciplina Estrutura de Dados I Professor Max Robert Marinho Curso Bacharelado em Ciência da Computação TurmaSemestre 3º sem 20222 DATA Data de entrega da atividade Alunos Descrever todos os alunos do grupo 1 Introdução Aqui deve conter a descrição da proposta da atividade explicando o objetivo da atividade o que deve ser feito e como 2 Fundamentação Teórica Aqui deve conter dividido por subcapítulos as descrições de CADA algoritmo implementado e utilizado na atividade Deve conter as explicações de funcionalidade de cada algoritmo os pseudocódigos de cada algoritmo implementado sua data de criação complexidade e quaisquer outras explicações pertinentes a cada algoritmo 3 Resultados e Discussão Aqui deve conter os testes realizados Deve conter a tabela de tempos obtidos e cada conjunto de gráficos solicitados Devem ser construídas discussões sobre os resultados obtidos 4 Conclusão Aqui deve conter o que foi considerado a partir das discussões do capítulo anterior 5 Referências Aqui deve conter todo o tipo de referência utilizada para a construção do trabalho Utilizar a formatação da ABNT para a construção desta etapa bem como a referenciação no meio do texto Algoritmos e Laboratório de Programação I Ano 2019 Prof Max Robert Marinho Página 1 Lista de Exercícios III ED I Data de entrega 11102024 As listas de exercícios são para serem resolvidas em duplas Cuidado com as cópias de trabalhos pois cópias surtirão na divisão de uma nota pela quantidade de trabalhos iguais As respostas aos problemas aqui tratados envolvem programação Sendo assim cada exercício é tratado como um programa diferente Somente os arquivosfonte devem ser enviados pelo SIGAA Para o envio é necessário se compactar TODOS os arquivos fontes construídos e então enviar este arquivo compactado pelo SIGAA Esta lista requer a entrega de um documento de análise dos tempos de execução dos programas de acordo com o tamanho da entrada de dados Este documento deve ser construído no Modelo de Relatório e postado no SIGAA juntamente com os códigos fonte Exercício o último conteúdo da disciplina de Estrutura de Dados I constou sobre a explicação e apresentação de algoritmos de ordenação e suas devidas análises de complexidade bem como seus algoritmos Para esta última lista de exercícios devem ser entregue implementações de diversos algoritmos de ordenação de forma CRESCENTE para diferentes conjuntos de dados e uma a análise dos tempos de execução de cada algoritmo Para isso seguem as regras do que se fazer Dos algoritmos de ordenação dados em sala de aula Insertion Sort Selection Sort Bubble Sort Merge Sort Quick Sort e Radix Sort 4 devem ser escolhidos para serem implementados Mais um algoritmo de ordenação deve ser escolhido para ser implementado o qual NÃO TENHA SIDO apresentado em sala de aula o Bogo Sort Combo Sort Heapsort Shell sort Bucket Sort Cocktail Sort Timsort Devem ser escritas descrições sobre cada algoritmo explicando um pouco sua funcionalidade quando foi criado complexidade e o algoritmo pseudocódigo que foi implementado Os testes devem ser gerados em cima de UM MESMO CONJUNTO DE DADOS ou seja todos os programas de ordenação irão ser executados com a mesma base de dados mesmo arquivo O conjunto de dados são arquivos que vocês mesmo devem construir por meio de OUTRO programa que irão gerar arquivos com 10 100 1000 10000 100000 1000000 e 10000000 de elementos inteiros distintos todos diferentes entre si o Devem ser construídos 3 conjuntos de dados com arquivos para cada quantidade diferente de elementos em um vetor visto item anterior Os elementos dispostos em cada conjunto de dados devem seguir a seguinte regra Conjunto 1 todos os elementos dos arquivos devem estar ordenados na ordem crescente Conjunto 2 todos os elementos dos arquivos devem estar ordenados na ordem decrescente Conjunto 3 os elementos dos arquivos devem estar dispostos de forma aleatória o O programa gerador de arquivos está no SIGAA Entenda o programa e configureo para que possa gerar os arquivos dos 3 conjuntos diferentes de dados para as mais diversas quantidades de elementos solicitados neste trabalho o O programa para ilustrar como adquirir o tempo de execução de uma instância de um programa também está no SIGAA Entenda o programa para que seja utilizado para adquirir o tempo de execução dos algoritmos de ordenação O tempo de execução a ser adquirido NÃO É DO PROGRAMA TODO mas SOMENTE da chamada da função de ordenação Cada algoritmo de ordenação deve ser executado 5 vezes para cada arquivo de tamanho diferente visto item anterior de cada conjunto de dados e calculada a média dos tempos de execução Deverão ser construídos gráficos para os tempos de execução obtidos o Para CADA conjunto de dados deverão ser construídos gráficos de TEMPO DE ALGORITMO x QTDE Deverão ser construídos 3 gráficos um para cada conjunto de dados Para cada gráfico deverão ser inseridas linhas que remetam a CADA algoritmo de ordenação Ao final cada gráfico terá 5 linhas onde poderá ver visualizado para CADA conjunto de dados a diferença de tempo de execução de CADA algoritmo de ordenação o Para CADA algoritmo de ordenação deve ser construído um gráfico de TEMPO x QTDE Cada conjunto de dados é uma nova linha de gráfico Cada linha do gráfico deverá ser obtida pelo tempo de execução do algoritmo para uma determinada quantidade de elementos dos arquivos de dados Ao final para CADA algoritmo os gráficos deverão conter 3 linhas que remetem cada uma a cada CONJUNTO de dados Ao final serão 5 gráficos com 3 linhas cada Tais gráficos servirão para se perceber o rendimento do algoritmo de acordo com cada conjunto de dados Todos os testes devem ser executados em UMA MESMA MÁQUINA No relatório deve constar as características da máquina como processador e sua frequência informações das caches IDE e linguagem utilizada compilador utilizado quantidade de memória qual sistema operacional e sua versão o NADA deve estar sendo executado na máquina ENQUANTO estiver executando os algoritmos de ordenação para que nenhuma outra tarefa possa atrapalhar no tempo de execução Não é obrigatório a implementação em C Caso a dupla deseje realizar em outra linguagem informe no documento de Modelo de Relatório desde que TODOS os algoritmos sejam construídos sob uma MESMA linguagem de programação Devese construir uma discussão dos resultados obtidos e finalizar com uma conclusão sobre o que foi discutido e alcançado GOVERNO DO ESTADO DE MATO GROSSO SECRETARIA DE CIÊNCIA E TECNOLOGIA UNIVERSIDADE DO ESTADO DE MATO GROSSO CAMPUS UNIVERSITÁRIO DE ALTO ARAGUAIA DEPARTAMENTO DE COMPUTAÇÃO Algoritmos e Laboratório de Programação I Ano 2019 Prof Max Robert Marinho Página 1 Disciplina Estrutura de Dados I Professor Max Robert Marinho Curso Bacharelado em Ciência da Computação TurmaSemestre 2º sem 20242 DATA 03102024 Alunos Rayse 1 Introdução Este trabalho visa implementar e analisar o desempenho das técnicas de ordenação Bubble Sort Insertion Sort Selection Sort Quick Sort e Heap Sort 2 Fundamentação Teórica 21 Bubble Sort Bubble Sort é um dos algoritmos de ordenação mais simples funciona repetidamente percorrendo a lista a ser ordenada comparando pares de elementos adjacentes e trocandoos de posição se estiverem na ordem errada Podemos ver o pseudocódigo e implementação a seguir Fonte Cormen et al 2002 GOVERNO DO ESTADO DE MATO GROSSO SECRETARIA DE CIÊNCIA E TECNOLOGIA UNIVERSIDADE DO ESTADO DE MATO GROSSO CAMPUS UNIVERSITÁRIO DE ALTO ARAGUAIA DEPARTAMENTO DE COMPUTAÇÃO Algoritmos e Laboratório de Programação I Ano 2019 Prof Max Robert Marinho Página 2 Fonte Acervo do autor 22 Insertion Sort A ordenação por inserção um algoritmo eficiente para ordenar um número pequeno de elementos A ordenação por inserção funciona da maneira como muitas pessoas ordenam as cartas em um jogo pôquer Iniciaremos com a mão esquerda vazia e as cartas viradas com a face para baixo na mesa Em seguida removeremos uma carta de cada vez da mesa inserindo a na posição correta na mão esquerda Cormen et al 2002 Fonte Cormen et al 2002 GOVERNO DO ESTADO DE MATO GROSSO SECRETARIA DE CIÊNCIA E TECNOLOGIA UNIVERSIDADE DO ESTADO DE MATO GROSSO CAMPUS UNIVERSITÁRIO DE ALTO ARAGUAIA DEPARTAMENTO DE COMPUTAÇÃO Algoritmos e Laboratório de Programação I Ano 2019 Prof Max Robert Marinho Página 3 Fonte Acervo do autor 23 Selection Sort O algoritmo divide a lista em duas partes uma parte ordenada e uma parte não ordenada Inicialmente a parte ordenada está vazia Para cada iteração ele busca o menor elemento na parte não ordenada do array O menor elemento encontrado é então trocado com o primeiro elemento da parte não ordenada movendoo para a parte ordenada Bubble Sort Insertion Sort e Selection Sort possui complexidade On² Fonte Acervo do autor GOVERNO DO ESTADO DE MATO GROSSO SECRETARIA DE CIÊNCIA E TECNOLOGIA UNIVERSIDADE DO ESTADO DE MATO GROSSO CAMPUS UNIVERSITÁRIO DE ALTO ARAGUAIA DEPARTAMENTO DE COMPUTAÇÃO Algoritmos e Laboratório de Programação I Ano 2019 Prof Max Robert Marinho Página 4 24 Quick Sort Segundo Cormen et al 2002 p117 o Quick Sort se baseia no paradigma de dividir e conquistar Ele seleciona um elemento chamado pivô e reorganiza o array de modo que todos os elementos menores que o pivô fique à esquerda e todos os elementos maiores fiquem à direita Fonte Cormen et al 2002 A chave para o algoritmo é o procedimento PARTITION que reorganiza o subarranjo no lugar veja o pseudocódigo abaixo Fonte Cormen et al 2002 A implementação do Quick Sort buscou seguir a lógica do pseudocódigo digo como podemos ver a seguir GOVERNO DO ESTADO DE MATO GROSSO SECRETARIA DE CIÊNCIA E TECNOLOGIA UNIVERSIDADE DO ESTADO DE MATO GROSSO CAMPUS UNIVERSITÁRIO DE ALTO ARAGUAIA DEPARTAMENTO DE COMPUTAÇÃO Algoritmos e Laboratório de Programação I Ano 2019 Prof Max Robert Marinho Página 5 Fonte Acervo do autor 25 Heap Sort A estrutura de dados heap binário é um objeto arranjo que pode ser visto como uma árvore binária praticamente completa cada nó da árvore corresponde a um elemento do arranjo que armazena o valor no nó A árvore está completamente preenchida em todos os níveis exceto talvez no nível mais baixo que é preenchido a partir da esquerda até certo ponto Cormen et al 2002 GOVERNO DO ESTADO DE MATO GROSSO SECRETARIA DE CIÊNCIA E TECNOLOGIA UNIVERSIDADE DO ESTADO DE MATO GROSSO CAMPUS UNIVERSITÁRIO DE ALTO ARAGUAIA DEPARTAMENTO DE COMPUTAÇÃO Algoritmos e Laboratório de Programação I Ano 2019 Prof Max Robert Marinho Página 6 Fonte Cormen et al 2002 Cormen et al 2002 p117 destaca que a MAXHEAPIFY é uma subrotina importante para manipulação de heaps máximos Suas entradas são um arranjo A e um índice i para o arranjo Quando MAXHEAPIFY é chamado supomos que as árvores binárias com raízes em LEFTi e RIGHTz são heaps máximos mas que Ai pode ser menor que seus filhos violando assim a propriedade de heap máximo A função de MAXHEAPIFY é deixar que o valor em Ai flutue para baixo no heap máximo de tal forma que a subárvore com raiz no índice i se torne um heap máximo A implimentação em C pode ser vista a seguir GOVERNO DO ESTADO DE MATO GROSSO SECRETARIA DE CIÊNCIA E TECNOLOGIA UNIVERSIDADE DO ESTADO DE MATO GROSSO CAMPUS UNIVERSITÁRIO DE ALTO ARAGUAIA DEPARTAMENTO DE COMPUTAÇÃO Algoritmos e Laboratório de Programação I Ano 2019 Prof Max Robert Marinho Página 7 Fonte Acervo do autor 3 Resultados e Discussão Os testes foram realizados em um notebook com processador IntelR CoreTM i7 GOVERNO DO ESTADO DE MATO GROSSO SECRETARIA DE CIÊNCIA E TECNOLOGIA UNIVERSIDADE DO ESTADO DE MATO GROSSO CAMPUS UNIVERSITÁRIO DE ALTO ARAGUAIA DEPARTAMENTO DE COMPUTAÇÃO Algoritmos e Laboratório de Programação I Ano 2019 Prof Max Robert Marinho Página 8 8565U CPU 180GHz 199 GHz RAM 160 GB Sistema operacional Windows 10 Home de 64 bits processador baseado em x64 Bubble Sort Insertion Sort e Selection Sort tiveram um desempenho significativamente pior à medida que o tamanho do vetor aumentou especialmente nos casos médios e piores Estes algoritmos são adequados para vetores pequenos mas ineficazes em grandes conjuntos de dados Nos testes o Insertion Sort mostrou ser o melhor dos três para o melhor caso pois tem um desempenho quase linear com vetores já ordenados enquanto Bubble Sort e Selection Sort mantêm uma complexidade mais alta Fonte Acervo do autor Para vetores pequenos ou ordenados os algoritmos On² podem ser suficientes mas para grandes conjuntos de dados Quick Sort e Heap Sort são mais adequados Quick Sort tende a ser o mais eficiente em média conforme pode ser visto no gráfico abaixo GOVERNO DO ESTADO DE MATO GROSSO SECRETARIA DE CIÊNCIA E TECNOLOGIA UNIVERSIDADE DO ESTADO DE MATO GROSSO CAMPUS UNIVERSITÁRIO DE ALTO ARAGUAIA DEPARTAMENTO DE COMPUTAÇÃO Algoritmos e Laboratório de Programação I Ano 2019 Prof Max Robert Marinho Página 9 Fonte Acervo do autor 4 Conclusão Cada algoritmo oferece diferentes vantagens e desvantagens dependendo do contexto em que são utilizados Ao comparar os algoritmos Bubble Sort Selection Sort Insertion Sort Quick Sort e Heap Sort é possível observar que eles se comportam de maneiras distintas em termos de eficiência facilidade de implementação e adequação para diferentes tipos de dados O Quick Sort e Heap Sort tiveram tempos de execução bem menores especialmente para vetores maiores devido à sua complexidade O n log n O Quick Sort é geralmente mais rápido conforme visto nos testes mas o Heap Sort oferece garantias de desempenho no pior caso A escolha do algoritmo de ordenação ideal depende do tamanho dos dados a necessidade de estabilidade e o cenário de aplicação como sistemas em tempo real ou dados que podem estar parcialmente ordenados 5 Referências GOVERNO DO ESTADO DE MATO GROSSO SECRETARIA DE CIÊNCIA E TECNOLOGIA UNIVERSIDADE DO ESTADO DE MATO GROSSO CAMPUS UNIVERSITÁRIO DE ALTO ARAGUAIA DEPARTAMENTO DE COMPUTAÇÃO Algoritmos e Laboratório de Programação I Ano 2019 Prof Max Robert Marinho Página 10 CORMEN Thomas H et al Algoritmos Teoria e Prática 2 ed Rio de Janeiro Elsevier 2002 Disponível em httpswwwcinufpebraraalgoritmos20portuguC3AAs 20cormenpdf Acesso em 3 out 2024 ZIVIANI N Projeto de Algoritmos com implementações em Pascal e C 2a edição Cengage Learning 2009