Analise Empirica de Algoritmos de Ordenacao em Listas Duplamente Encadeadas

ESTRUTURA DE DADOS Problema Comparando empiricamente o tempo de execução de algoritmos de ordenação em listas duplamente encadeadas Devese implementar os seguintes algoritmos de ordenação em c BubbleSort InsertionSort SelectionSort MergeSort QuickSort 1 Uma versão para cada um dos cinco algoritmos acima usando lista duplamente encadeada de inteiros A lista duplamente encadeada deve ser obrigatoriamente programada como uma classe usando programação orientada a objetos 2 Preste bastante atenção Como nos implementamos nossas listas encadeadas usando programação orientada a objetos não temos acesso a estrutura interna da lista Porém esses algoritmos ficarão muito mais rápidos se eles forem implementados tendo acesso a estrutura interna da lista encadeada Assim uma dica para realizar esse trabalho de modo eficiente e decente é implementar os algoritmos acima como funçõesmembros da classe que implementa a lista duplamente encadeada Você pode usar a lista duplamente encadeada iniciada em sala ou pode implementar a sua do zero Deste modo quando você tivesse um objeto lista duplamente encadeada chamado myList e invocasse myListbubblesort a sua lista myList seria ordenada pelo bubblesort que você programou para ela 3 Testes Você deve comparar diferentes estratégias de ordenação para ordenar um conjunto de N inteiros positivos aleatoriamente gerados Realize experimentos considerando listas de inteiros aleatoriamente geradas com tamanho N 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 11000 12000 13000 14000 15000 16000 17000 18000 19000 20000 21000 22000 23000 24000 25000 26000 27000 28000 29000 30000 31000 32000 33000 34000 35000 36000 37000 38000 39000 40000 41000 42000 43000 44000 45000 46000 47000 48000 49000 50000 51000 52000 53000 54000 55000 56000 57000 58000 59000 60000 61000 62000 63000 64000 65000 66000 67000 68000 69000 70000 71000 72000 73000 74000 75000 76000 77000 78000 79000 80000 81000 82000 83000 84000 85000 86000 87000 88000 89000 90000 91000 92000 93000 94000 95000 96000 97000 98000 e 99000 4 Para cada valor de N realize experimentos com 5 sementes diferentes Para a comparação dos algoritmos de ordenação avalie os valores médios do tempo de execução 1 5 No relatório você deve apresentar uma pequena comparação entre os algoritmosimplementações Discuta os resultados e conclusões obtidas No seu experimento qual algoritmo teve melhor desempenho Você sabe dizer por que Você sabe interpretar os resultados obtidos Observação Juntamente com esta descrição do trabalho foi disponibilizado um pequeno exemplo 2 com a implementação usual do algoritmo BubbleSort e de um outro algoritmo que ordena vetores de inteiros chamado CocktailSort 6 No programaexemplo 495 vetores de inteiros gerados aleatoriamente são ordenados usando os algoritmos BubbleSort e CocktailSort são 495 porque são gerados 5 vetores de tamanho N para cada um dos 99 possíveis valores de N listados acima logo 495 99 5 No programa fornecido são calculados os valores médios dos tempos de execução Para cada valor de N estipulado acima são gerados 5 vetores aleatórios de tamanho N e a média do tempo das cinco execuções do algoritmo sobre esses cinco vetores de tamanho N e armazenada em um arquivo Para cada execução do CocktailSort e do BubbleSort é calculada a média do seu tempo de execução em microssegundos e esses dados são gravados em arquivos chamados resultadoCocktailtxt e resultadoBubbletxt que encontramse na pasta resultados Cada um desses arquivos e composto de duas colunas a primeira indica o tamanho do vetor e a segunda indica o tempo medio em microssegundos que o respectivo algoritmo levou para ordenar o respectivo vetor 7 Informações adicionais Deverá ser submetido juntamente com o código um relatório técnico contendo 1 Uma descrição breve das principais características de cada um dos 5 algoritmos de ordenação que foram programados como por exemplo i qual a complexidade de pior caso ii são estáveis iii são algoritmos in loco iv são recursivos ou iterativos v Qual a ideia principal do algoritmo Como ele faz para ordenar o vetor 2 Uma explicacao do algoritmo que voce pesquisou e implementou 3 Uma seção de dificuldades encontradas 4 Uma seção de bibliografia contendo as referências utilizadas Se você con sultar algum site da internet vídeo ou livro coloque esta fonte de pesquisa no seu trabalho Não há porque omitir as consultas 5 Relatório formato PDF Relatório Estrutura de Dados Francisco Matheus dos Santos Cavalcante A ordenação de um conjunto de objetos é necessária em diversas situações e contextos O processo de ordenação consiste em colocar os objetos em uma ordem específica crescente ou decrescente com base em um critério de ordenação Na computação a ordenação de objetos é ainda mais comum e essencial Os algoritmos de ordenação são amplamente utilizados como parte de outros algoritmos sendo considerado um dos passos necessários Existem vários algoritmos de ordenação clássicos documentados na literatura Neste trabalho focaremos na implementação e testes de alguns desses algoritmos clássicos considerando a ordenação em ordem crescente dos objetos O primeiro algoritmo é o Bubble Sort Este algoritmo iterativo percorre repetidamente o conjunto de objetos verificando se o objetoi é maior do que o objetoi1 Caso essa condição seja verdadeira os objetos são trocados de posição A ideia do algoritmo é que a cada iteração o maior objeto seja colocado na última posição uma troca por vez O Bubble Sort possui uma complexidade de tempo média pior e melhor caso de On 2 Este algoritmo é estável e in loco O segundo algoritmo é o Selection Sort Este algoritmo iterativo seleciona a cada iteração o objeto de maior valor do vetor não ordenado e o insere na última posição do vetor ordenado O Selection Sort possui uma complexidade de tempo média pior e melhor caso de On 2 Este algoritmo não é estável mas é in loco O terceiro algoritmo é o Insertion Sort Este algoritmo iterativo percorre o vetor buscando inserir cada elemento em sua posição correta em relação aos elementos já processados O Insertion Sort possui uma complexidade de tempo melhor caso de On que ocorre quando há apenas uma quantidade constante de objetos não ordenados Já a complexidade de tempo média e pior caso é de On 2 Este algoritmo é estável e in loco O quarto algoritmo é o Merge Sort Este algoritmo recursivo utiliza a estratégia de Divisão e Conquista A ideia do algoritmo é dividir o conjunto de objetos em duas partes ordenar cada parte de forma recursiva e em seguida mesclar os dois subconjuntos usando um procedimento chamado Merge que garante que o conjunto resultante esteja ordenado O Merge Sort possui uma complexidade de tempo média pior e melhor caso de On logn Este algoritmo é estável mas não é in loco O quinto algoritmo é o QuickSort A ideia deste algoritmo é selecionar um elemento chamado de pivô e dividir o conjunto em dois subconjuntos elementos menores e maiores que o pivô Os dois subconjuntos são ordenados recursivamente O QuickSort possui uma complexidade de tempo melhor e médio caso de On logn No pior caso sua complexidade de tempo é On 2 O pior caso ocorre quando o pivô é sempre o menor ou o maior elemento do conjunto ainda não ordenado Este algoritmo é estável e in loco O sexto algoritmo é o Counting Sort que se baseia na contagem da frequência dos objetos Após a contagem o algoritmo percorre o vetor cujo tamanho é dado pelo tamanho do conjunto de possíveis objetos e insere os objetos na lista de forma ordenada O Counting Sort possui uma complexidade de tempo média pior e melhor caso de On considerando o tamanho do conjunto de possíveis objetos como constante No entanto o algoritmo pode encontrar problemas de falta de memória quando o número de possíveis objetos é muito grande Este algoritmo é estável mas não é in loco O objetivo deste trabalho é comparar a eficiência desses seis algoritmos na prática Para isso foram gerados vetores aleatórios de inteiros Foram gerados vetores com tamanhos nos seguintes conjuntos de valores 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 11000 12000 13000 14000 15000 16000 17000 18000 19000 20000 30000 40000 50000 60000 70000 80000 90000 100000 É importante ressaltar que o conjunto de testes foi reduzido devido ao tempo de execução especialmente dos algoritmos com complexidade quadrática Para cada tamanho foram geradas cinco instâncias a partir de diferentes sementes O tempo de execução de cada algoritmo foi obtido pela média aritmética das cinco execuções Cada algoritmo foi executado para cada uma das 28 x 5 140 instâncias Os algoritmos foram implementados na linguagem C utilizando a estrutura de lista duplamente encadeada Para cada execução de um algoritmo o tempo médio de execução por tamanho do vetor foi salvo Os valores aleatórios gerados foram limitados a um valor limite máximo aplicando a operação do resto da divisão Isto foi necessário devido ao algoritmo Counting Sort O gráfico a seguir apresenta o resumo dos resultados obtidos Entre os algoritmos de ordenação com caso médio quadrático se destacou o Insertion Sort isso devese ao fato de realizar menos operações que os demais quando o vetor está quase ordenado O QuickSort apresentou resultados um pouco melhores que o MergeSort acredito que isto aconteça devido ao fato do Quick não ser necessário criar memórias adicionais como o Merge O algoritmo que apresentou melhores resultados foi o Counting Sort pois ele é o que apresenta a menor complexidade em relação aos demais Vale destacar que só foi possível usar este algoritmo devido a limitação dos elementos possíveis pois caso contrário o mesmo não poderia sequer ter sido utilizado Referências CORMEN T H et al Algoritmos teoria e prática Editora Campus v 2 p 296 2002 Relatório Estrutura de Dados Francisco Matheus dos Santos Cavalcante A ordenação de um conjunto de objetos é necessária em diversas situações e contextos O processo de ordenação consiste em colocar os objetos em uma ordem específica crescente ou decrescente com base em um critério de ordenação Na computação a ordenação de objetos é ainda mais comum e essencial Os algoritmos de ordenação são amplamente utilizados como parte de outros algoritmos sendo considerado um dos passos necessários Existem vários algoritmos de ordenação clássicos documentados na literatura Neste trabalho focaremos na implementação e testes de alguns desses algoritmos clássicos considerando a ordenação em ordem crescente dos objetos O primeiro algoritmo é o Bubble Sort Este algoritmo iterativo percorre repetidamente o conjunto de objetos verificando se o objetoi é maior do que o objetoi1 Caso essa condição seja verdadeira os objetos são trocados de posição A ideia do algoritmo é que a cada iteração o maior objeto seja colocado na última posição uma troca por vez O Bubble Sort possui uma complexidade de tempo média pior e melhor caso de Este algoritmo é estável e in loco 𝑂𝑛 2 O segundo algoritmo é o Selection Sort Este algoritmo iterativo seleciona a cada iteração o objeto de maior valor do vetor não ordenado e o insere na última posição do vetor ordenado O Selection Sort possui uma complexidade de tempo média pior e melhor caso de Este algoritmo não é estável mas é in loco 𝑂𝑛 2 O terceiro algoritmo é o Insertion Sort Este algoritmo iterativo percorre o vetor buscando inserir cada elemento em sua posição correta em relação aos elementos já processados O Insertion Sort possui uma complexidade de tempo melhor caso de que ocorre quando há apenas uma quantidade constante de 𝑂𝑛 objetos não ordenados Já a complexidade de tempo média e pior caso é de 𝑂𝑛 2 Este algoritmo é estável e in loco O quarto algoritmo é o Merge Sort Este algoritmo recursivo utiliza a estratégia de Divisão e Conquista A ideia do algoritmo é dividir o conjunto de objetos em duas partes ordenar cada parte de forma recursiva e em seguida mesclar os dois subconjuntos usando um procedimento chamado Merge que garante que o conjunto resultante esteja ordenado O Merge Sort possui uma complexidade de tempo média pior e melhor caso de Este algoritmo é 𝑂𝑛 𝑙𝑜𝑔 𝑛 estável mas não é in loco O quinto algoritmo é o QuickSort A ideia deste algoritmo é selecionar um elemento chamado de pivô e dividir o conjunto em dois subconjuntos elementos menores e maiores que o pivô Os dois subconjuntos são ordenados recursivamente O QuickSort possui uma complexidade de tempo melhor e médio caso de No pior caso sua complexidade de tempo é O pior caso 𝑂𝑛 𝑙𝑜𝑔 𝑛 𝑂𝑛 2 ocorre quando o pivô é sempre o menor ou o maior elemento do conjunto ainda não ordenado Este algoritmo é estável e in loco O sexto algoritmo é o Counting Sort que se baseia na contagem da frequência dos objetos Após a contagem o algoritmo percorre o vetor cujo tamanho é dado pelo tamanho do conjunto de possíveis objetos e insere os objetos na lista de forma ordenada O Counting Sort possui uma complexidade de tempo média pior e melhor caso de considerando o tamanho do conjunto de 𝑂𝑛 possíveis objetos como constante No entanto o algoritmo pode encontrar problemas de falta de memória quando o número de possíveis objetos é muito grande Este algoritmo é estável mas não é in loco O objetivo deste trabalho é comparar a eficiência desses seis algoritmos na prática Para isso foram gerados vetores aleatórios de inteiros Foram gerados vetores com tamanhos nos seguintes conjuntos de valores 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 11000 12000 13000 14000 15000 16000 17000 18000 19000 20000 30000 40000 50000 60000 70000 80000 90000 100000 É importante ressaltar que o conjunto de testes foi reduzido devido ao tempo de execução especialmente dos algoritmos com complexidade quadrática Para cada tamanho foram geradas cinco instâncias a partir de diferentes sementes O tempo de execução de cada algoritmo foi obtido pela média aritmética das cinco execuções Cada algoritmo foi executado para cada uma das 28 x 5 140 instâncias Os algoritmos foram implementados na linguagem C utilizando a estrutura de lista duplamente encadeada Para cada execução de um algoritmo o tempo médio de execução por tamanho do vetor foi salvo Os valores aleatórios gerados foram limitados a um valor limite máximo aplicando a operação do resto da divisão Isto foi necessário devido ao algoritmo Counting Sort O gráfico a seguir apresenta o resumo dos resultados obtidos Entre os algoritmos de ordenação com caso médio quadrático se destacou o Insertion Sort isso devese ao fato de realizar menos operações que os demais quando o vetor está quase ordenado O QuickSort apresentou resultados um pouco melhores que o MergeSort acredito que isto aconteça devido ao fato do Quick não ser necessário criar memórias adicionais como o Merge O algoritmo que apresentou melhores resultados foi o Counting Sort pois ele é o que apresenta a menor complexidade em relação aos demais Vale destacar que só foi possível usar este algoritmo devido a limitação dos elementos possíveis pois caso contrário o mesmo não poderia sequer ter sido utilizado Referências CORMEN T H et al Algoritmos teoria e prática Editora Campus v 2 p 296 2002