Quicksort
O Quicksort é um algoritmo de ordenação de dados extremamente rápido e eficiente, concebido por C.A.R. Hoare em 1960 durante sua visita à Universidade de Moscou como estudante. Hoare desenvolveu o Quicksort enquanto trabalhava em um projeto de tradução de máquina para o National Physical Laboratory, buscando ordenar palavras para um dicionário inglês-russo. Sua ideia central era decompor um problema grande em subproblemas menores e mais fáceis de resolver. Após refinamentos, o algoritmo foi formalmente publicado em 1962.
Pontos-chave
- O Quicksort foi inventado por C.A.R. Hoare em 1960 para ordenar palavras em um dicionário.
- Ele utiliza a estratégia de 'divisão e conquista' para ordenar listas de forma eficiente.
- A performance do Quicksort é fortemente influenciada pela escolha do pivô e do método de particionamento.
- No pior caso, sua complexidade pode ser O(n²), mas no melhor e médio caso é O(n log n).
- Versões como o Dual-Pivot Quicksort buscam otimizar ainda mais o desempenho do algoritmo.
O Quicksort emprega a estratégia de 'divisão e conquista'. Ele reorganiza os elementos de uma lista de forma que os 'menores' precedam os 'maiores' em relação a um elemento pivô. Em seguida, o algoritmo ordena recursivamente as duas sublistas resultantes (de elementos menores e maiores) até que a lista completa esteja ordenada. O caso base da recursão são listas de tamanho zero ou um, que já são consideradas ordenadas. O processo é garantido como finito, pois a cada iteração, pelo menos um elemento é posicionado em sua posição final e não é mais manipulado. A escolha do pivô e a implementação do método de particionamento são cruciais e afetam significativamente a performance do algoritmo.
Método de Partição de Lomuto
Atribuído a Nico Lomuto e popularizado por Bentley e Cormen et al., este método de particionamento geralmente escolhe um pivô no início ou no final do array. Ele recebe dois índices, 'lo' e 'hi', que definem a porção do array a ser particionada. Um índice 'i' é selecionado, e outro índice 'j' percorre o array, realizando trocas quando necessário. O objetivo é garantir que todos os elementos menores ou iguais ao pivô fiquem antes do índice 'i', e os elementos de 'i + 1' até 'hi' (ou 'j - 1') sejam maiores que o pivô. Embora seja mais simples e fácil de entender, sendo frequentemente usado como introdução ao Quicksort, é menos eficiente que o método de Hoare. Em casos onde o array já está ordenado ou contém apenas elementos iguais, este método pode degenerar para uma complexidade de O(n²). Existem várias técnicas para melhorar sua eficiência, como aprimorar a escolha do pivô, lidar com elementos iguais e usar algoritmos diferentes (como o Insertion Sort) para arrays pequenos.
Imagem: Wikipedia:en:User:RolandH · BY-SA · Openverse
A complexidade do Quicksort varia significativamente dependendo de como o algoritmo particiona a lista. Analisar os cenários de pior e melhor caso nos ajuda a entender seus limites de desempenho.
Comportamento no Pior Caso
O pior cenário de particionamento ocorre quando o elemento pivô divide a lista de forma desbalanceada, resultando em duas sublistas: uma com tamanho 0 e outra com tamanho 'n - 1' (onde 'n' é o tamanho da lista original). Isso acontece quando o pivô é o menor ou o maior elemento da lista, como em listas já ordenadas ou inversamente ordenadas. Se essa situação se repete em todas as chamadas recursivas, cada etapa processará uma lista de tamanho igual à anterior menos um. A relação de recorrência para este caso é T(n) = T(n - 1) + T(0) + θ(n), simplificando para T(n - 1) + θ(n), o que resulta em uma complexidade de O(n²).
Comportamento no Melhor Caso
O melhor cenário de particionamento acontece quando o pivô divide a lista em duas sublistas de tamanhos aproximadamente iguais, não maiores que n/2 (uma com tamanho [n/2] e outra com [n/2] - 1). Neste caso, o Quicksort atinge sua maior velocidade. A relação de recorrência é T(n) ≤ 2T(n/2) + θ(n), que, pelo teorema mestre, tem solução T(n) = O(n log n).
Imagem: en:User:RolandH · BY-SA · Openverse
Em 2009, Yaroslavskiy propôs o Dual-Pivot Quicksort, uma tentativa de aprimorar a eficiência do Quicksort clássico. Este método utiliza dois pivôs para particionar um array de entrada em três partes. Yaroslavskiy demonstrou que o uso de dois pivôs é mais eficaz, especialmente com grandes volumes de dados, superando o algoritmo Quicksort clássico. O Dual-Pivot Quicksort particiona arrays de diferentes tipos de dados primitivos (como int, char, double, float e long) em três seções usando dois pivôs (P1 e P2). Ele estabelece ponteiros como L, K, G, e índices 'left' e 'right' para os elementos inicial e final. Yaroslavskiy também mostrou que para a ordenação de dados primitivos, o Quicksort de 3 partições é mais eficiente, com um número médio de comparações de (2)n ln(n) e um número médio de trocas de (0,8)n ln(n). Em comparação, a versão clássica do Quicksort tem (2)n ln(n) comparações e (1)n ln(n) trocas em média.
Imagem: RolandH (redrawn in SVG by Stkl) · BY-SA · Openverse
O Quicksort pode ser visto como uma versão otimizada de uma árvore binária ordenada. Em vez de inserir itens sequencialmente em uma árvore explícita, ele os organiza implicitamente na árvore por meio de chamadas recursivas, realizando as mesmas comparações, mas em uma ordem diferente. O algoritmo mais similar ao Quicksort é o Heapsort. No pior caso, o Heapsort tem uma complexidade de O(n log n), o que é melhor que o pior caso do Quicksort. No entanto, em média, o Heapsort tende a ser mais lento que o Quicksort, embora essa afirmação tenha sido amplamente debatida. O Quicksort mantém seu problema de pior caso, exceto na variante IntroSort, que detecta o pior caso e muda para Heapsort. Se for sabido de antemão que o Heapsort será necessário, é mais eficiente usá-lo diretamente do que usar o IntroSort e depois chamar o Heapsort.
Imagem: avlxyz · BY-NC-SA · Openverse
O Quicksort pode ser implementado em diversas linguagens de programação, seguindo a lógica de particionamento e recursão. Abaixo, apresentamos exemplos de como o algoritmo pode ser codificado em diferentes contextos.
Pseudocódigo
Em pseudocódigo, o Quicksort para ordenar elementos de um array A do índice i₀ até Hᵢ pode ser representado da seguinte forma, ilustrando a lógica fundamental do algoritmo.
Python
Uma implementação do algoritmo na linguagem Python 3 pode ser escrita de forma concisa, aproveitando as características da linguagem para expressar a lógica recursiva e de particionamento.
C++
Uma versão em C++ do pseudocódigo inicial pode ser expressa, mostrando como os valores são desorganizados e, em seguida, organizados pela função quicksort. Há também uma implementação padrão mais detalhada deste algoritmo na função `qsort` da biblioteca C.
Haskell
Em Haskell, uma linguagem de programação funcional, o algoritmo Quicksort pode ser escrito de uma maneira elegante e declarativa. Partindo de uma lista inicial como [10,2,5,3,1,6,7,4,2,3,4,8,9], o resultado seria a lista ordenada.
