# 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. ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586090466/a10290d3-4010-4716-8fc4-b65d59558f23.png) 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. ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586091937/f05822b2-a2fd-4bf6-aea3-e2049ad244b4.png) 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. ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586094051/5195328a-abf0-4d07-be67-675cd27dfc0d.png) 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. ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586095573/5c2bacf4-226e-47d9-bf60-144eea312205.png) 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ô. ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586097406/11e39580-eeee-46e7-84a2-fac3b07437e7.png) Vamos escolher o 2 como pivô. ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586099064/22e0a07e-fcb2-4d68-917c-5d84a92b907d.png) Agora somos obrigados a escolher o 3 como pivô. ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586100502/7bcf8627-69bb-4cf2-921f-c820c064fe67.png) Agora que chegamos no caso base, vamos ordenar os subarrays recursivamente. Voltando agora os arrays até organizarmos o array da esquerda. ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586102188/0b523144-1510-49ae-8b14-de4164606250.png) Agora vamos organizar o array da direita. ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586103296/3d7d40e5-e410-4ff6-b42c-5e41372a229a.png) 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. ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586105219/9aacc718-2522-4392-800a-0111b53d6cf0.png) Agora que chegamos no caso base, vamos ordenar os subarrays recursivamente. Voltando agora os arrays até organizarmos o array da direita. ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586108528/2a0e8dcd-a3ec-4a26-b4fe-1221e875c665.png) Agora que organizamos os subarrays, o array original está ordenado. ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586110191/caaef6a6-ec30-4b91-ab22-9d7ad14273e2.png) 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](https://medium.com/@sschonss/introdu%C3%A7%C3%A3o-a-algoritmos-nota%C3%A7%C3%A3o-big-o-d1d555b5e0e9). 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](https://github.com/sschonss/quicksort). 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!