Merge e Quick Sort: entenda qual é o melhor algoritmo

Nos artigos referentes à implementação dos dois algoritmos em questão, percebemos que ambos possuem sua complexidade em O(N lg N). Mas questionamos a eficiência do QuickSort em todos cenários? Será que ele sempre executa em O(N lg N)? Vamos fazer uma análise.

Retornado ao funcionamento do QuickSort, devemos escolher um item pivô para garantir seu local correto na lista e então passar por todos os itens menores à esquerda e itens maiores à direita (dependendo da ordenação desejada).

Executando isso de forma recursiva teremos uma lista devidamente ordenada.

Mas qual seria o pior caso?

Vamos tomar como base a implementação que fizemos do [QuickSort](Link do artigo de implementação do QuickSort), no qual escolhemos sempre o item na extremidade inferior como pivô.

Imagine que recebemos uma lista já ordenada como entrada do algoritmo. Note o seguinte comportamento:

Notamos que em cada escolha de pivô percorremos todo o restante da lista em busca da real posição do mesmo. Isso nos lembra algo, não lembra? A cada iteração de escolha, percorremos a lista, o que nos parece um comportamento quadrático. Sendo assim, no pior caso o QuickSort se comporta como O(N²).

Então consideramos o QuickSort sempre pior que o MergeSort? Não necessariamente! Vimos que o pior caso se deu pela escolha do pivô. Neste mesmo cenário, se escolhermos o pivô como o item do meio da lista, a cada iteração entraremos no melhor caso do algoritmo, que executa em O(N lg N) assim como no caso médio. E agora percebemos que é bem pouco provável cairmos no pior caso do QuickSort.

Por isso devemos avaliar e considerar os mais diversos fatores e requisitos para a escolha do algoritmo que nos atenderá da melhor forma.

Outras limitações

Agora vamos supor que estamos em um projeto com recursos de memória volátil escassos, o que torna o cuidado com a utilização de memória um requisito não-funcional (requisitos referentes ao desempenho, disponibilidade, manutenção e recursos do projeto). Qual algoritmo escolher?

Vimos que o MergeSort cria uma lista temporária do mesmo tamanho da original, duplicando assim a alocação de memória. Talvez esta não fosse a melhor solução para este cenário, não acha?

Conclusão

Vimos que quando se trata de algoritmos com a mesma complexidade na maior parte dos cenários, devemos avaliar outros fatores para a escolha da solução que melhor se adequa ao contexto no qual estaremos inseridos.

E dessa forma finalizamos essa série de artigos mostrando a importância do estudo de algoritmos e como eles podem afetar nossos projetos. Espero que possamos nos ver em breve, até mais!