1. 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ê?

Passo 1

O enunciado apresenta a variação mediana de três do quicksort, em que, antes de particionar, a gente toma os elementos
A[\text{início}],\;A[\text{meio}],\;A[\text{fim}]í
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.

Passo 2

Vamos modelar o custo de tempo do quicksort comum. Se T(n) é o tempo médio para ordenar um array de tamanho n com um pivô “aleatório” ou fixo, temos aproximadamente
T(n)=T(k)+T(n-1-k)+O(n),
onde O(n) corresponde ao custo de particionar o array em torno do pivô. Em média, k\approx n/2, o que leva a
T(n)=2T\bigl(n/2\bigr)+O(n)\quad\Longrightarrow\quad T(n)=O(n\log n).

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 O(n) comparações e trocas.
Portanto o novo tempo médio satisfaz
T(n)=T(k)+T(n-1-k)+\bigl(O(n)+O(1)\bigr)\;=\;T(k)+T(n-1-k)+O(n).
Ou seja, a parte assintótica não muda: continua O(n\log n) em média e O(n^2) 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 O(n) 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.

Exercícios relacionados