Quicksort

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.

Performance

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!