Metodologias de Ordenação de Algoritmos: Uma Análise Comparativa do Tempo de Execução
Os algoritmos de ordenação são procedimentos computacionais que organizam um conjunto de dados de uma maneira específica. Eles são amplamente utilizados para uma variedade de tarefas, incluindo a organização de dados em bancos de dados, o processamento de grandes volumes de dados e a classificação de resultados de pesquisas na internet. Ao escolher um algoritmo de ordenação, você deve pensar no tamanho dos dados, na complexidade da lista e na eficiência necessária para concluir a tarefa. Para conjuntos de dados mais pequenos, algoritmos mais simples, como a insertion sort e o bubble sort, funcionam melhor. Por outro lado, algoritmos mais complexos, como selection sort e quick sort, funcionam melhor com conjuntos de dados maiores.
Introdução
No presente estudo, objetiva-se analisar e comparar as metodologias de ordenação de algoritmos mais comumente empregadas, avaliando o tempo de execução de cada uma. As metodologias em questão incluem o Bubble Sort, Selection Sort, Insertion Sort, Shell Sort, Quick Sort e Merge Sort. O tempo de execução de cada algoritmo será meticulosamente medido e comparado para fornecer insights sobre sua eficiência e desempenho relativo.
Para conduzir esta análise, cada algoritmo será submetido a testes, utilizando-se vetores de dados de diversos tamanhos e naturezas, abrangendo dimensões que variam de 1000 a um limite determinado pelo desempenho computacional, incluindo 10000, 30000, 50000, 70000, 100000 até onde as capacidades computacionais do sistema permitirem. O tempo necessário para ordenar cada vetor será registrado e analisado.
Apresentação dos algoritmos e Notação Big(O):
Os Algoritmos:
Esses algoritmos foram usados nos testes. Usamos a liguagem C++ para testar suas capacidades computacional e praticidade, vou deixar o link do meu repositório do codigo que utilizamos, um pouco mais a frente vamos nos aprofundar mais sobre o codigo.
Notação Big(O)
Na ciência da computação, a notação big(O), ou grande O, é usada para descrever o desempenho assintótico (para todos os valores suficientemente grandes) de um algoritmo. É uma maneira de calcular o tempo de execução de um algoritmo em relação ao tamanho da entrada do problema.
O que significa? A complexidade do pior caso de um algoritmo é representada pela notação Big(O). o tempo necessário para resolver um problema. Essa notação explica como o tempo aumentará se o problema aumentar também. Naturalmente, ter conhecimento disso é útil porque nos permite comparar algoritmos com várias complexidades, selecionar o mais adequado para uma tarefa específica e garantir que o tempo de execução seja otimizado.
Tipo de bolha
É um algoritmo de ordenação simples, este método percorre todo o vetor várias vezes, comparando cada elemento com seu vizinho, levando o maior elemento para o fim da sequência, fazendo isso n vezes até que o vetor esteja ordenado corretamente. Apesar de ser um dos mais fáceis de se implementar e de compreender, o Bubble sort é ineficiente para vetores grandes, os quais são usados outros algoritmos de ordenação como: Merge Sort e Quick Sort. Possui complexidade O(n²), o qual seu tempo de execução aumenta exponencialmente conforme o tamanho do vetor.
Veja o exemplo de sua funcionalidade:
Complexidade Computacinal:
A complexidade computacional do Bubble Sort é de O(n²) no pior caso e no caso médio. No melhor caso, quando a lista já está ordenada, a complexidade é de O(n). Isso significa que, em média, o tempo de execução do algoritmo cresce quadráticamente com o tamanho da lista a ser ordenada. Assim como o Selection Sort, o Bubble Sort não é eficiente para grandes conjuntos de dados.
Ordenação por seleção
Selection sort é um algoritmo de ordenação simples e intuitivo. Ele funciona selecionando repetidamente o menor (ou maior, dependendo da ordem desejada) elemento de uma lista não ordenada e movendo-o para o início da lista ordenada. O processo continua até que todos os elementos sejam colocados em suas posições corretas. Apesar de ser simples de entender e implementar, o selection sort não é eficiente em termos de tempo de execução, especialmente em listas grandes, devido ao seu tempo de execução quadrático no pior caso. No entanto, pode ser útil em situações onde a memória é limitada ou em listas pequenas.
Veja o exemplo de sua funcionalidade:
Complexidade Computacional:
A complexidade computacional do Selection Sort é de O(n²) no pior caso, no caso médio e no melhor caso. Isso significa que o tempo de execução do algoritmo cresce quadráticamente com o tamanho da lista a ser ordenada. O Selection Sort é considerado um dos algoritmos de ordenação mais simples, mas não é eficiente para grandes conjuntos de dados.
Classificação de inserção
O insertion sort é outro algoritmo de ordenação simples, mas um pouco mais eficiente do que o selection sort em alguns casos. Ele funciona de forma semelhante à maneira como muitas pessoas ordenam cartas de baralho em suas mãos. O insertion sort é eficiente em listas pequenas ou quase ordenadas, pois tem um desempenho de tempo de execução quadrático no pior caso, mas pode ter um desempenho próximo de linear em listas quase ordenadas. No entanto, assim como o selection sort, não é uma escolha ideal para listas muito grandes devido ao seu desempenho de tempo de execução.
Veja o exemplo de sua funcionalidade:
Complexidade Computacional:
A complexidade computacional do Insertion Sort é de O(n²) no pior caso e no caso médio. No entanto, no melhor caso, quando a lista já está ordenada, a complexidade é de O(n), tornando o Insertion Sort mais eficiente que o Bubble Sort e o Selection Sort nesse cenário específico.
Classificação de casca
O shell sort é um algoritmo de ordenação mais avançado que tenta melhorar o desempenho do insertion sort ao tomar vantagem da ideia de que os elementos de uma lista que estão longe uns dos outros estão parcialmente ordenados. Ele é uma generalização do insertion sort. O shell sort é mais eficiente do que o insertion sort e o selection sort em muitos casos, especialmente para listas maiores. No entanto, sua eficiência depende do espaçamento inicial escolhido, e ainda assim pode ser superado por algoritmos de ordenação mais avançados, como o merge sort ou o quick sort, em certos cenários.
Veja o exemplo de sua funcionalidade, usaremos outra forma de GIF para o melhor entendimento e funcionalidade.
Complexidade Computacional:
A complexidade computacional do Shell Sort depende do intervalo de lacunas (gaps) utilizado. No pior caso, a complexidade é de aproximadamente O(n²), mas pode variar dependendo da sequência de lacunas escolhida. No entanto, em muitos casos, o Shell Sort apresenta um desempenho melhor do que outros algoritmos de ordenação com complexidade O(n²), especialmente para conjuntos de dados maiores.
Ordenação rápida
O quick sort é um dos algoritmos de ordenação mais eficientes e amplamente utilizados. Ele utiliza o método de divisão e conquista para ordenar uma lista de elementos. A ideia central do quick sort é selecionar um elemento, chamado de “pivô”, e particionar a lista em dois subconjuntos: um contendo elementos menores que o pivô e outro contendo elementos maiores que o pivô. Em seguida, o algoritmo é aplicado recursivamente a esses subconjuntos. O quick sort tem uma eficiência média de tempo de execução de O(n log n), tornando-o muito rápido na prática, especialmente para grandes conjuntos de dados. No entanto, o pior caso de tempo de execução é O(n²), que ocorre quando o pivô escolhido está constantemente entre os maiores ou menores elementos, levando a uma partição desbalanceada. Existem técnicas para mitigar isso, como a escolha de pivôs aleatórios ou a técnica de “pivôs triplos”.
Veja o exemplo de funcionalidade:
Complexidade computacional:
A complexidade computacional do Quick Sort depende da escolha do pivô e da distribuição dos elementos no conjunto de dados. Em média, o Quick Sort tem uma complexidade de tempo de O(n log n), onde n é o número de elementos a serem ordenados. No entanto, no pior caso, quando o pivô é sempre o menor ou o maior elemento da lista não ordenada, a complexidade pode ser de O(n²). O Quick Sort é geralmente rápido e eficiente na prática, especialmente para grandes conjuntos de dados.
Mesclar classificação
O merge sort é outro algoritmo de ordenação eficiente que utiliza a abordagem de divisão e conquista. Ele divide recursivamente a lista não ordenada em metades iguais, ordena cada metade separadamente e, em seguida, combina as duas metades ordenadas para produzir a lista final ordenada. O merge sort é eficiente porque sua complexidade de tempo é sempre O(n log n), independentemente do arranjo dos elementos na lista. Isso faz com que seja uma escolha ideal para ordenar grandes conjuntos de dados. No entanto, o merge sort requer espaço adicional para armazenar as duas metades durante o processo de ordenação, o que pode ser uma desvantagem em termos de uso de memória, especialmente para listas muito grandes.
Veja o exemplo de sua funcionalidade:
Complexidade computacional:
A complexidade computacional do Merge Sort é sempre O(n log n), independentemente da distribuição dos elementos no conjunto de dados ou do tamanho da lista. Isso faz do Merge Sort um algoritmo muito eficiente para ordenação, especialmente para conjuntos de dados grandes.
Existe diferenças entre eles?
Buscamos estratégias para avaliar suas habilidades, e para isso, adaptamos um código fornecido pelo nosso professor de Estruturas de Dados para gerar números aleatórios de 1 a 100, caso queira verificar o codigo vou deixar o link do repositório para verificar. Esses números foram utilizados para preencher os vetores que utilizamos nos testes. Modificamos o código para que ele também nos fornecesse o tempo necessário para ordenar os vetores de diferentes tamanhos. No entanto, os resultados eram originalmente apresentados em microssegundos, o que refletia a capacidade computacional quase instantânea com vetores pequenos. Portanto, decidimos converter os resultados para segundos, para uma melhor compreensão dos resultados.
Aqui está o algoritmo que usamos para escolher os numeros aleatórios de 1 a 100:
Um exemplo de como medimos o tempo de execução de cada algoritmo está presente neste código,onde utilizamos uma biblioteca chamada <chrono> para medir o tempo, que atualmente mostra a medição para o algoritmo de ordenação com Selection Sort. Realizamos medições individuais para os seis algoritmos, mas o procedimento foi semelhante para todos eles.
Após executarmos o código cinco vezes para obter uma média de cada método, obtivemos os seguintes resultados. Criamos uma tabela para facilitar o entendimento:
Gráficos
Os gráficos foram montados com a ajuda da ferramenta Google Colab. Essa ferramenta permite escrever documentos de caderno usando o Jupyter Notebook, um ambiente interativo integrado com python que permite o trabalho com dados, e também criar gráficos usando a biblioteca matplotlib. Ao exibir os valores no eixo vertical do gráfico, optamos por abreviar (arredondar) os valores de tempo, os quais estão originalmente em segundos.
De acordo com a curva de crescimento de cada algoritmo, é evidente que os três algoritmos iniciais, cuja complexidade é O(n²), estão crescendo rapidamente. A curva de crescimento desses algoritmos se acentua progressivamente à medida que o tamanho do problema aumenta, diminuindo que seu desempenho é fortemente impactado pelo tamanho da entrada. Em cada gráfico há o desvio padrão também onde esse desvio padrão seria uma medida estatística que indica o grau de dispersão dos dados em relação à média. Ele fornece uma indicação de quão longe os valores individuais do conjunto de dados tendem a se afastar da média.
Gráfico 1:
Gráfico 2:
Gráfico 3:
Com exceção da variação significativa do Shell Sort, observamos que a frase do “dividir para conquistar” começa a fazer sentido, cuja complexidade é O(n log n). Nesses casos, o gráfico mostra uma curva mais suave em relação aos algoritmos de complexidade O(n²), que aumenta com o tamanho do problema. Isso indica que esses algoritmos podem ser mais escaláveis e eficientes do que seus equivalentes O(n2) em problemas mais complexos. Essa abordagem pode permitir um processamento mais rápido e eficiente, por isso é especialmente importante para aplicações que lidam com grandes conjuntos de dados ou que precisam de alto desempenho.
Gráfico 4:
Gráfico 5:
Além disso, comparar diretamente os algoritmos é a melhor maneira de entender como eles afetam o desempenho. O algoritmo de insertion sort foi demonstrado como o mais eficiente com complexidade O(n²), enquanto o algoritmo de Merge sort foi demonstrado como o mais ineficiente com complexidade O(n log n). Esses dois algoritmos foram escolhidos para demonstrar que, embora um seja considerado o “melhor” e o outro o “pior” em suas respectivas complexidades, é possível observar uma diferença notável ao comparar os gráficos dos dois algoritmos.
Gráfico 6:
Gráfico 7:
O gráfico a ser apresentado a seguir é uma comparação entre os resultados dos gráficos anteriores, demonstrando o desempenho relativo de cada método em relação aos demais.
Quando os gráficos 1, 2, 3, 4, 5 e 6 foram mostrados, todos parecem muito semelhantes. Isso deveu-se ao fato de que os intervalos de tempo mudaram entre eles. O comportamento de todos os algoritmos apresentados e testados pode ser facilmente apresentado colocando todos no mesmo plano e compartilhando os mesmos momentos. O desempenho dos métodos de Merge Sort, shell sort e de Quick sort foi tão semelhante ao que o gráfico 8 mostra apenas uma linha.
Conclusão:
Os algoritmos de ordenação mais antigos, como o bubble sort e o Selection Sort, são mais fáceis de usar e são úteis para fins educacionais e para lidar com conjuntos de dados menores. No entanto, a complexidade desses algoritmos se torna rapidamente um obstáculo para o desempenho à medida que o tamanho dos dados aumenta, tornando-os inadequados para aplicações em larga escala. Por outro lado, algoritmos mais complexos, como o Merge Sort e a Quick sort, são mais eficazes ao lidar com grandes volumes de dados, o que os torna ideais para programas que exigem altas velocidades.
A análise dos resultados mostra as diferenças no desempenho entre os algoritmos de ordenação. Basta comparar o Bubble Sort e o Quick Sort na tarefa de ordenar uma lista com 100 mil valores para demonstrar essa diferença. O Bubble Sort precisou de aproximadamente 1,26 minutos, enquanto o Quick Sort precisou de aproximadamente 0,235, onde observa-se nitidamente a agilidade e superioridade do quick sort em comparação com o bubble sort.
Veja o no gráfico abaixo a comparação de como os 6 métodos se saiu com o vetor de tamanho de 100 mil.
Observa-se que os três últimos métodos são significativamente mais rápidos, chegando a uma compilação quase instantânea dos vetores. Embora pareçam ter o mesmo tempo de execução, há uma diferença de milissegundos entre eles. É evidente que o Quick Sort, Merge Sort e Shell Sort são extremamente eficientes e rápidos.
Assim, concluindo, existe uma grande diferença entre os algoritmos de ordenação em termos de desempenho, complexidade, complexidade de implementação e outros fatores.
Os gráficos mostrados e os dados coletados mostram a eficiência de cada algoritmo. As diferenças entre os algoritmos são visíveis. Os dados foram feitos com listas de mil a cem mil elementos, mas essas listas são consideradas pequenas para computação. Apesar disso, esses testes nos deram uma ideia de como cada algoritmo funcionaria em situações reais.
Referências:
Introdução aos algoritmos. Geeksforgeeks. Disponível em: https://www.geeksforgeeks.org/sorting-algorithms/. Acessado em: 10, abril de 2024.
File: Sorting shellsort anim2.gif. Wikimedia commons. 16 November 2020. Disponível em: https://commons.m.wikimedia.org/wiki/File:Sorting_shellsort_anim2.gif. Acesso em: 10 de Abril de 2024.
Google Colab. Google. Disponível em: https://colab.research.google.com/. Acesso em: 10 de Abril de 2024.
La Vivien Post. 21 de junho de 2023. Disponível em: https://www.lavivienpost.net/. Acesso em: 05 de Abril de 2024.
Chrono in C++. Geeksforgeeks. 20 jan, 2023. Disponível em: https://www.geeksforgeeks.org/chrono-in-c/. Acesso em: 10 de Abril de 2024.
Daniel Rosa. Shen Huang. O que é a notação Big O: complexidade de tempo e de espaço. freeCodeCamp. 15 de Dezembro de 2021. Disponível em: https://www.freecodecamp.org/portuguese/news/o-que-e-a-notacao-big-o-complexidade-de-tempo-e-de-espaco/. Acesso em: 14 de Abril de 2024.