Dificuldade ★★☆
5 minutos de Leitura 🕒
O Quicksort é um algoritmo de ordenação por comparação geral criado por Tony Hoare em 1959. Ele é um algoritmo de Divisão e Conquista que funciona particionando e reordenando recursivamente um arranjo de acordo com um elemento pivô.
O Quicksort apresenta um desempenho marginalmente superiora outros algoritmos de ordenação por comparação, como o Merge Sort e o Heap Sort.
Para lidar com chaves duplicadas, o passo 3 usa 3 sub-arranjos, de forma que os elementos que forem menores do que o pivô ficam no primeiro sub-arranjo, os elementos iguais ao pivô ficam no sub-arranjo do meio, e os elementos maiores que o pivô ficam no terceiro sub-arranjo.
O pior caso do Quicksort ocorre quando o arranjo de entrada já está ordenado. Nesse caso, ao fim do particionamento do particionamento os sub-arranjos podem ter tamanhos diferentes (estarem desbalanceados), fazendo com que a ordenação recursiva de um sub-arranjo leve mais tempo que a do outro. Nessa situação, o algoritmo tem um custo quadrático de comparações, em função do número de elementos a serem ordenados:
O(n²) comparaçõesO melhor caso do Quicksort ocorre quando o arranjo de entrada está desordenado de forma randomizada. Nessa situação, o algoritmo tem um custo super-linear de comparações, em função do número de elementos a serem ordenados:
O(n log₂ n) comparaçõesO desempenho do Quicksort é impactado pela forma como o elemento pivô é escolhido. Se uma escolha ruim é feita, ao fim do particionamento do particionamento os sub-arranjos podem ter tamanhos diferentes (estarem desbalanceados), fazendo com que a ordenação recursiva de um sub-arranjo leve mais tempo que a do outro. Existem três estratégias populares para a escolha do elemento pivô, cada uma com suas vantagens e desvantagens:
Durante o passo de particionamento é importante garantir que os elementos que estão sendo comparados estejam dentro do intervalo considerado. Caso contrário, o algoritmo não funcionará corretamente. Apesar desse detalhe de implementação poder ser resolvido com comparações adicionais na etapa de particionamento, isso incorre em um sobrecusto na execução do Quicksort.
Uma solução alternativa para atacar esse problema é inserir elementos sentinelas em ambos os extremos do arranjo, que por construção garantem que os elementos sempre estarão dentro do intervalo válido do arranjo. Para tanto, o elemento na extrema esquerda do arranjo pode ser substituído pelo elemento pivô, e na extrema direita pode-se adicionar um elemento que seja maior que todos os demais elementos no arranjo.
Conforme o Quicksort realiza chamadas recursivas, o tamanho do arranjo de trabalho diminui até ter apenas um elemento (caso base da recursão). Enquanto essa característica recursiva não é um problema em teoria, na prática ela incorre em um sobrecusto dominante no tempo de execução do algoritmo, quando o arranjo de trabalho é pequeno demais.
Uma forma de evitar esse problema é modificar a implementação original do Quicksort de forma que, quando o arranjo de trabalho for pequeno, a recursão é interrompida e um algoritmo iterativo é usado. O limiar para a parada de recursão bem como algoritmo iterativo a ser utilizado dependem caso a caso. No entanto, vale considerar que popularmente utiliza-se o limiar de 10 a 20 elementos e o Insertion Sort (Ordenação por Inserção) como algoritmo de ordenação.
O Quicksort apresenta uma complexidade quadrática quando lida com um arranjo cheio de chaves duplicadas. Ele pode ser modificado usando um algoritmo de partição tripla, tornando esse caso em complexidade linear. Essa solução foi inspirada no problema da bandeira da Holanda, um desafio de programação proposto por Edsger Dijkstra em 1976.
Veja o código completo no GitHub.