Please enable JavaScript.
Coggle requires JavaScript to display documents.
M5 (Levitin) - Coggle Diagram
M5 (Levitin)
Cap. 5
.2
Um dos mais eficientes métodos de ordenação baseado no método Dividir e Conquistar é o:
Quicksort
Consiste na ordenação da sequência através da ordenação recursiva de subsequências, tal qual o
mergesort
.
No entanto, ao invés de buscar uma divisão em arrays de mesmo tamanho, a separação ocorre em relação à um elemento
"pivô"
(
pivot
), que já está posicionado corretamente
Numa abordagem mais simples, o pivô escolhido é sempre o primeiro elemento da subsequência. Para encontrar a sua posição correta, separa-se a array em dois grupos: o dos elementos menores ou iguais ao pivô e o dos elementos maiores ou iguais ao pivô (os elementos iguais ao pivô acabam ficando na "interseção" dos 2 grupos), posicionando então o pivô entre os dois grupos. Em seguida, cada grupo sofre recursivamente o mesmo procedimento de particionamento
Para separar a array nesses 2 grupos, vasculha-se a subsequência da direita para esquerda buscando um elemento maior ou igual ao pivô. Encontrando um elemento desse tipo, vasculha-se então a array da direita para a esquerda buscando um elemento menor ou igual ao pivô.
Em seguida, como os elementos menores devem estar no grupo da esquerda e os maiores à direita, troca-se a posição dos elementos encontrados e a busca continua
A busca então finaliza quando o elemento maior que o pivô estiver à direita do elemento menor que o pivô, pois isso indica que todos os elementos à esquerda são necessariamente menores ou iguais ao pivô e todos à direita são necessariamente maiores ou iguais ao pivô.
Por fim, o pivô troca de posição com esse último elemento menor encontrado, de maneira que este fique no começo da array e o pivô fique numa posição onde todos à esquerda são menores ou iguais a ele e todos à direita são maiores ou iguais a ele. Assim, o pivô já está corretamente posicionado na sequência total de elementos.
3 more items...
Se a implementação do algoritmo seguir a ordem "incrementar/decrementar -> verificar", a busca da direita para esquerda deve começar uma posição à mais do tamanho da array.
Nota-se que se todos os elementos à direita do pivô forem menores do que ele, então a busca precisa ser informada de alguma forma sobre quando parar. Nesse caso, é interessante o uso de um "sentinela"
Algumas modificações que podem aumentar o desempenho do
quicksort
são:
Seleção otimizada do pivô, optando por um elemento aleatório da array (
randomized quicksort
), ou ainda escolhendo um elemento próximo à média entre o primeiro, o último e o intermediário elementos de uma subsequência (
median-of-three
)
Utilização do
insertion sort
na ordenação de subsequências pequenas (entre 5 a 15 elementos), ou então a não ordenação dessas sequências pequenas com a aplicação final do
insertion sort
sobre a sequência parcialmente ordenada
Aumento do número de particionamentos em uma mesma subsequência, como por exemplo dividindo em 3 grupos: os menores, os maiores e os de mesmo tamanho que o pivô
Dentre as suas desvantagens, destacam-se:
Não é estável (elementos de mesmo tamanho podem ficar em posições relativas entre si diferentes da inicial
Requer o uso de uma pilha para armazenar parâmetro de subsequências ainda a serem ordenadas
Apesar da eficiência espacial possa chegar a Ο(log n), não se equipara ao O(1) do
heapsort
Embora as chances sejam baixas, ainda é possível que o algoritmo execute um número de comparações em θ(n^2)
O desempenho depende não só dos detalhes de implementação do algoritmo mas também da arquitetura do computador e dos
data types