Quicksort é um algoritmo de ordenação muito eficiente, inventado por C.A.R. Hoare em 1960. Ele é amplamente utilizado para ordenação de arrays. O algoritmo que apresentamos a seguir é uma versão recursiva do Quicksort que seleciona um elemento como pivô e particiona o array de forma que todos os elementos menores que o pivô fiquem antes dele e os maiores fiquem depois. Os subarrays são então ordenados recursivamente.
Mas antes de começarmos a falar sobre o algoritmo, você precisa entender o que são métodos de DC (Divisão e Conquista).
Métodos de DC
Métodos de DC são algoritmos que resolvem um problema dividindo-o em subproblemas, resolvendo os subproblemas recursivamente e combinando as soluções dos subproblemas para resolver o problema original.
Vamos ver um exemplo de um algoritmo que utiliza DC.
Exemplo
Imagina que você tenha um array de inteiros e quer saber a soma de todos os elementos desse array. Você pode resolver esse problema utilizando DC da seguinte forma:
Array: [1, 2, 3, 4, 5]
Qual é o caso base? O caso base é quando o array tem apenas um elemento. Nesse caso, a soma é o próprio elemento.
Como iremos chegar no caso base? Vamos remover um elemento e ver o que sobra.
Agora que chegamos no caso base, vamos resolver o problema. A soma de todos os elementos do array [5] é 5. Agora, vamos somar o 4 que removemos anteriormente. A soma de todos os elementos do array [4, 5] é 9. Agora, vamos somar o 3 que removemos anteriormente. A soma de todos os elementos do array [3, 9] é 12. E assim por diante.
A soma de todos os elementos do array [1, 2, 3, 4, 5] é 15.
Esse é um caso simples de DC e muitos algoritmos utilizam esse conceito para resolver problemas.
Por que não usar um loop?
Você pode estar se perguntando por que não usar um loop para resolver esse problema. E a resposta é: você pode! Mas, em alguns casos, a solução utilizando DC é mais simples e mais fácil de entender.
Outro ponto importante é que, em algumas linguagens, principalmente as funcionais, não existe a estrutura de repetição (for, while, etc). Então, a única forma de resolver um problema é utilizando DC.
Entendendo esse algoritimo, você consegue trabalhar com outras linguagens de programação e entender como elas funcionam.
Caso tenha alguma dúvida, busque por mais exemplos e tente resolver problemas utilizando DC.
Quicksort
Agora que você entendeu o que é DC, vamos falar sobre o Quicksort.
O Quicksort é um algoritmo de ordenação muito eficiente, inventado por C.A.R. Hoare em 1960. Ele é amplamente utilizado para ordenação de arrays. O algoritmo que apresentamos a seguir é uma versão recursiva do Quicksort que seleciona um elemento como pivô e particiona o array de forma que todos os elementos menores que o pivô fiquem antes dele e os maiores fiquem depois. Os subarrays são então ordenados recursivamente.
Exemplo
Vamos ver um exemplo de como o Quicksort funciona.
Passo 1: Escolha um elemento como pivô. Vamos escolher o 6.
Passo 2: Particione o array de forma que todos os elementos menores que o pivô fiquem antes dele e os maiores fiquem depois.
Passo 3: Ordenar os subarrays recursivamente.
O que significa ordenar os subarrays recursivamente? Significa que vamos repetir os passos 1 e 2 para os subarrays, escolhendo um pivô e particionando o array.
Vamos escolher o 1 como pivô.
Vamos escolher o 2 como pivô.
Agora somos obrigados a escolher o 3 como pivô.
Agora que chegamos no caso base, vamos ordenar os subarrays recursivamente.
Voltando agora os arrays até organizarmos o array da esquerda.
Agora vamos organizar o array da direita.
Passo 1: Escolha um elemento como pivô. Vamos escolher o 10.
Passo 2: Particione o array de forma que todos os elementos menores que o pivô fiquem antes dele e os maiores fiquem depois.
Agora que chegamos no caso base, vamos ordenar os subarrays recursivamente.
Voltando agora os arrays até organizarmos o array da direita.
Agora que organizamos os subarrays, o array original está ordenado.
Esse é um exemplo de como o Quicksort funciona.
Dentro do desenvolvimento de software, a performance é um fator muito importante e muitas vezes usamos a Notação Big O para descrever a eficiência de um algoritmo.
Caso você não conheça a Notação Big O, recomendo que você leia um artigo sobre o assunto que escrevi aqui nesse link: Notação Big O.
O desempenho do Quicksort é O(n log n) no melhor caso e O(n²) no pior caso.
E a performance vai depender do pivô que você escolher. Se você escolher um pivô que seja o menor ou o maior elemento do array, o desempenho do Quicksort será O(n²). Mas, se você escolher um pivô que seja o elemento do meio do array, a performance do Quicksort será O(n log n).
Mas como escolher o pivô? Existem várias formas de escolher o pivô e a escolha do pivô vai depender do seu problema. Uma forma de escolher o pivô é escolher o elemento do meio do array.
Dessa forma, eu fiz um repositório no github com a implementação do Quicksort em Go. Caso você queira ver a implementação, clique aqui.
Esse artigo é uma introdução ao Quicksort e espero que você tenha entendido como o algoritmo funciona, e agora se você escutar alguém falando sobre Quicksort, você vai entender do que se trata.
Lembre-se que a prática leva a perfeição e, quanto mais você praticar, mais você vai entender sobre o assunto.
Caso tenha alguma dúvida, busque por mais exemplos e tente resolver problemas utilizando Quicksort.
Espero que você tenha gostado do artigo e até a próxima!
