Quicksort vs Mergesort vs Heapsort: Análise de desempenho

No desenvolvimento de software, entender o desempenho dos algoritmos de ordenação é essencial para construir soluções eficientes, especialmente ao lidar com grandes volumes de dados. Neste artigo, vamos explorar o desempenho de três dos algoritmos de ordenação mais conhecidos: Quicksort vs Mergesort vs Heapsort. Nosso objetivo é fornecer uma visão clara de como esses algoritmos se comportam em diferentes situações, ajudando você a escolher o mais adequado para suas necessidades.

O que são Algoritmos de Ordenação?

Todo algoritmo que tem como objetivo receber como entrada uma lista de valores, e fornecer como saída essa mesma lista seguinda uma ordem específica, seja ela crescente ou decrescente, é considerado um algoritmo de ordenação.

Algoritmos de ordenação são parte fundamental do aprendizado de programação, e são utilizados em diversos problemas reais no dia a dia, portanto entender bem os conceitos e o funcionamento dos principais algoritmos de ordenação é fundamental para a formação de um bom profissional de desenvolvimento de software.

O Quicksort, Mergesort e Heapsort são amplamente utilizados por sua eficiência e versatilidade. Cada um deles tem características distintas que os tornam adequados para diferentes tipos de conjuntos de dados.

Quicksort

O Quicksort é um algoritmo de ordenação recursivo que utiliza a técnica de “divisão e conquista”. Ele seleciona um pivô, particiona o array em torno desse pivô e, em seguida, aplica a mesma lógica nas subpartições. Com uma complexidade média de O(nlog⁡n), o Quicksort geralmente é rápido para a maioria dos casos. No entanto, sua eficiência cai drasticamente quando a entrada contém muitos elementos repetidos, devido a natureza da função de partição, nesse caso o algoritmo tende a ir para o seu pior caso que é O(n²).

Mergesort

O Mergesort também segue a técnica de “divisão e conquista”, mas ao invés de particionar em torno de um pivô, ele divide o array sempre ao meio, ordena as duas metades chamando o mesmo algoritmo recursivamente e depois as mescla. Ele oferece uma complexidade estável de O(nlog⁡n) em todos os casos, o que o torna uma escolha robusta para grandes volumes de dados, independentemente da estrutura dos mesmos.

Heapsort

O Heapsort utiliza uma estrutura de dados chamada heap para ordenar o array. Sua complexidade também é O(nlog⁡n), mas seu comportamento é mais próximo do Quicksort em termos de eficiência para entradas com dados mais simples. Ele é particularmente eficiente em situações onde não há muitos elementos repetidos.

Testes de desempenho: Quicksort vs Mergesort vs Heapsort

Para realizar a comparação entre esses algoritmos, realizamos testes com entradas de diferentes tamanhos: 10.000, 100.000, 1.000.000, 10.000.000 e 100.000.000. Para cada tamanho, rodamos os três algoritmos em 50 vetores de inteiros entre 0 e 65535, e também em vetores com apenas 0 e 1 dispostos aleatoriamente para validar o desempenho dos algoritmos em cenários com muitos valores repetidos.

Testes com inteiros aleatórios entre 0 e 65535

Entradas de tamanho 10.000

O desempenho dos três algoritmos foi muito semelhante para entradas de tamanho 10.000, o que mostra que para entradas pequenas podemos utilizar qualquer um dos três algoritmos sem nenhuma visível diferença de desempenho.

Entradas de tamanho 100.000

Nos testes com entradas de tamanho 100.000, os três algoritmos tiveram desempenho semelhante. O quicksort se destacou com um desempenho ligeiramente melhor, mas como os tempos ficaram abaixo de 1 décimo de segundo, ainda é possível usar qualquer um dos três sem notar diferenças significativas no tempo de execução.

Entradas de tamanho 1.000.000

Para as entradas de tamanho 1.000.000 o algoritmo Heapsort acabou tendo um desempenho inferior aos outros dois, mas os tempos de execução, assim como a diferença entre os tempos foram todos inferiores a 1 segundo. Por isso, ainda podemos utilizar qualquer um dos três algoritmos sem notar diferenças significativas de desempenho.

Entradas de tamanho 10.000.000

Nos testes realizados com entradas de tamanho 10.000.00, já foi possível observar uma boa diferença de desempenho entre os algoritmos. O algoritmo Mergesort foi o que apresentou o melhor desempenho, a média de tempo do algoritmo é próxima da metade da média dos outros dois. O Quicksort teve a pior média entre os três algoritmos. Essa queda no desempenho ocorre porque, à medida que o tamanho da entrada aumenta, também aumenta a quantidade de números repetidos no vetor. Isso afeta a função de partição, fazendo o quicksort se aproximar de seu pior caso.

Entradas de tamanho 100.000.000

Nos testes realizados com entradas de tamanho 100.000.000, houve um aumento maior ainda na diferença de desempenho entre os três algoritmos. Mais uma vez o Mergesort obteve o melhor desempenho dos três algoritmos. A maior diferença foi no desempenho do Quicksort, que levou em média 23 minutos para ordenar cada entrada. Isso confirma a análise feita nos testes com entradas de 10.000.000 elementos: quanto maior a quantidade de elementos repetidos nos vetores, pior o desempenho do Quicksort.

Conclusão dos testes

Os testes revelaram comportamentos interessantes:

1. Para entradas menores (até 1.000.000 elementos), o desempenho dos três algoritmos foi muito semelhante. Nessas situações, qualquer um dos três pode ser usado sem grandes diferenças em termos de tempo de execução.
2. A partir de 10.000.000 elementos, o Mergesort se destacou, apresentando desempenho significativamente melhor, enquanto o Quicksort sofreu com a alta repetição de valores, se aproximando do seu pior caso, com complexidade O(n²).
3. Para 100.000.000 elementos, a diferença ficou ainda mais pronunciada. O Mergesort continuou sendo o mais rápido, enquanto o Quicksort teve um desempenho muito ruim, levando em média 23 minutos para completar a ordenação.

Testes realizados com entradas contendo apenas 0 e 1

Mergesort

Para as entradas contendo apenas os inteiros 0 e 1, não foi observada nenhuma alteração no comportamento do algoritmo Mergesort com relação aos testes realizados com entradas com inteiros entre 0 e 65535, as médias obtidas sofreram pouca alteração quando comparadas com as médias obtidas nos primeiros experimentos. No gráfico abaixo é possível visualizar as médias muitos próximas em ambos os cenários:

Heapsort

Nos testes realizados com o Heapsort, houve uma visível diferença de desempenho com relação aos testes realizados com entradas contendo inteiros até 65535. Para as entradas contendo apenas os inteiros 0 e 1 o Heapsort foi o algoritmo que apresentou o melhor desempenho dos três. Possivelmente essa melhora significativa no desempenho seja pelo fato de que com muitos elementos repetidos, é necessário um número menor de chamadas da função Heapfy, para montar a árvore Heap no vetor, tornando a ordenação muito mais rápida, se aproximando de seu melhor caso na maioria das vezes.

Quicksort

Os testes anteriores mostraram que o Quicksort sofre muito com entradas que possuem muitos valores repetidos. Por isso, esperava-se um desempenho ruim para entradas com apenas 0 e 1, e os resultados confirmaram essa expectativa. Para as entradas com 0 e 1, o algoritmo terá o mesmo comportamento em todos os casos. A função de partição dividirá a entrada em duas partes, e depois ordenará cada uma dessas partições de maneira quadrática.
Os testes foram realizados apenas com entradas de tamanho 10.000 e 100.000. Para tamanhos maiores, o programa apresentou erro após 23 minutos de execução. Isso provavelmente ocorreu devido à implementação recursiva, que excedeu o limite de memória disponível devido ao grande número de recursões.

Considerações Finais

Compreender os algoritmos de ordenação e suas características é crucial para otimizar o desempenho de sistemas que lidam com grandes volumes de dados. Em situações reais, a escolha do algoritmo certo pode impactar drasticamente o tempo de processamento.

Para desenvolvedores, o Mergesort é uma aposta segura, especialmente para entradas grandes e variadas. Por outro lado, o Quicksort continua sendo rápido e eficiente em muitos cenários; no entanto, deve ser evitado quando lidamos com grandes volumes de dados repetidos. Além disso, o Heapsort é uma excelente alternativa, sobretudo quando a repetição de elementos está controlada.

Andrew Cavalcante Pacífico

Bacharel em Ciência da Computação pela Universidade Federal do Amazonas, MBA em Gerenciamento de Projetos pela Fundação Getúlio Vargas.

Atualmente trabalha como Gerente de Engenharia na Meliuz.

Com 20 anos de experiência na área, já trabalhou com um pouco de tudo, C, C++, Java, C#, Delphi, Node.js, AWS, PHP, Python, React, Angular, jQuery, e mais um monte de coisa que nem existe mais 😀

andrewpacifico.com