- O quicksort mediana de três é uma variação do quicksort que tenta minimizar o problema de pivôs ruins. Seu princípio é o seguinte:
a. Ordene os elementos A[inicio], A[meio], A[fim] do array
b. Escolha o A[meio] como pivô, traga ele para a primeira posição
c. Aplique o quicksort normalmente ao array (de inicio até fim)
Essa variação degrada a performance do quicksort? Por quê?
a. Ordene os elementos A[inicio], A[meio], A[fim] do array
b. Escolha o A[meio] como pivô, traga ele para a primeira posição
c. Aplique o quicksort normalmente ao array (de inicio até fim)
Passo 1
O enunciado apresenta a variação mediana de três do quicksort, em que, antes de particionar, a gente toma os elementos
ordena-os (por exemplo com 3 comparações) e escolhe o que ficou no meio como pivô. Depois traz esse pivô para a primeira posição e aplica o quicksort normalmente.
O conteúdo aqui é analisar como essa escolha de pivô afeta a complexidade e o desempenho prático do quicksort.
O conteúdo aqui é analisar como essa escolha de pivô afeta a complexidade e o desempenho prático do quicksort.
Passo 2
Vamos modelar o custo de tempo do quicksort comum. Se
é o tempo médio para ordenar um array de tamanho
com um pivô “aleatório” ou fixo, temos aproximadamente
onde
corresponde ao custo de particionar o array em torno do pivô. Em média,
, o que leva a
Passo 3
Agora, ao usar mediana de três, em cada chamada recursiva a gente ainda faz:
a) Ordenar três elementos para achar a mediana – esse passo custa um número constante de comparações e, eventualmente, algumas trocas (digamos até 3 comparações e 2 trocas).
b) Particionar em comparações e trocas.
Portanto o novo tempo médio satisfaz
a) Ordenar três elementos para achar a mediana – esse passo custa um número constante de comparações e, eventualmente, algumas trocas (digamos até 3 comparações e 2 trocas).
b) Particionar em
Portanto o novo tempo médio satisfaz
Ou seja, a parte assintótica não muda: continua
em média e
no pior caso.
Passo 4
Apesar de a complexidade assintótica não piorar, a seleção da mediana de três introduz um overhead constante em cada chamada (as comparações extras para ordenar três números). Na prática:
- Para vetores grandes, esse custo extra é pequeno perto dos
do particionamento e costuma valer a pena porque o pivô fica melhor (partições mais balanceadas). - Para vetores muito pequenos, o overhead de tirar a mediana de três pode superar o ganho das partições, e aí o algoritmo fica até um pouco mais lento que a versão simples.
Resposta
Sim, essa variação degrada o desempenho por um fator constante: a cada chamada recursiva adicionam-se comparações e trocas extras para ordenar três elementos, o que aumenta o tempo de execução prático, embora não altere a complexidade assintótica do quicksort.