Algoritmos de ordenação baseados em dividir para conquistar.
2. O que mais afeta a performance do quicksort?
2. O que mais afeta a performance do quicksort?
Passo 1
O enunciado pede para identificarmos qual fator mais impacta a performance do QuickSort, que é um algoritmo de ordenação do tipo “dividir para conquistar”. Para resolver isso, precisamos entender como o QuickSort divide o problema em partições e como essa divisão afeta o número de comparações e a profundidade da recursão.
Passo 2
No QuickSort, escolhemos um elemento chamado pivô e particionamos o vetor em dois subvetores: um com valores menores que o pivô e outro com valores maiores que o pivô. Em seguida, aplicamos recursivamente o mesmo procedimento a cada subvetor. A eficiência depende de quão uniformemente essas partições são feitas.
Passo 3
A complexidade média do QuickSort é
, mas no pior caso ela chega a
. Esse pior caso ocorre quando as partições são muito desbalanceadas, por exemplo, se o pivô for sempre o menor ou o maior elemento do subvetor.
Passo 4
Portanto, o que mais afeta a performance do QuickSort é a escolha do pivô, pois ela determina o tamanho relativo das partições em cada nível de recursão. Se o pivô dividir o vetor quase ao meio em todas as chamadas, a profundidade da recursão fica em torno de
e o custo total das partições é
. Se o pivô for muito tendencioso, formamos subvetores de tamanho próximo a
e a recursão terá profundidade
, resultando em
comparações.
Passo 5
Além da escolha pura do pivô, influenciam também a estrutura dos dados de entrada (por exemplo, vetores já ordenados ou com muitos elementos iguais) e a técnica de seleção do pivô (como pivô aleatório, mediana de três ou amostragem). Essas estratégias buscam aproximar as partições de tamanhos equivalentes e reduzir a probabilidade de casos degenerados.
Resposta
O fator que mais afeta a performance do QuickSort é a estratégia de escolha do pivô, pois ela define a qualidade das partições e, consequentemente, o número de comparações e a profundidade da recursão.