# Quicksort - Author: Luiz Schons - Published: 2024-02-28 - URL: https://luizschons.com/pt-br/posts/quicksort/ - English: https://luizschons.com/posts/quicksort.md - Temas: Algoritmos 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.

Elemento removido	Array restante
1	[2, 3, 4, 5]
2	[3, 4, 5]
3	[4, 5]
4	[5]

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.

Caso base	Soma
[5]	5
[4, 5]	9
[3, 9]	12
[2, 12]	14
[1, 14]	15

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 algoritmo, 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.

Array
3, 6, 8, 10, 1, 2, 1

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.

Menores que 6	Pivô	Maiores que 6
3, 1, 2, 1	6	8, 10

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ô.

Menores que 1	Pivô	Maiores que 1
	1, 1	2, 3

Vamos escolher o 2 como pivô.

Menores que 2	Pivô	Maiores que 2
	2	3

Agora somos obrigados a escolher o 3 como pivô.

Menores que 3	Pivô	Maiores que 3
	3

Agora que chegamos no caso base, vamos ordenar os subarrays recursivamente. Voltando agora os arrays até organizarmos o array da esquerda.

Menores que 6	Pivô	Maiores que 6
1, 1, 2, 3	6	8, 10

Agora vamos organizar o array da direita.

Array
8, 10

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.

Menores que 10	Pivô	Maiores que 10
8	10

Agora que chegamos no caso base, vamos ordenar os subarrays recursivamente. Voltando agora os arrays até organizarmos o array da direita.

Array
8, 10

Agora que organizamos os subarrays, o array original está ordenado.

Array
1, 1, 2, 3, 6, 8, 10

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 à 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!