- Implemente o algoritmo de Quicksort. Modifique a escolha do pivô (sempre o primeiro, o último, o elemento do meio ou uma escolha aleatória) e analise o impacto dessa escolha no tempo de execução.
Passo 1
Beleza, vamos resolver esse exercício sobre o algoritmo de Quicksort! A gente vai precisar entender como o Quicksort funciona, especialmente como a escolha do pivô pode afetar o tempo de execução. Vamos implementar o Quicksort com diferentes estratégias para escolher o pivô: sempre o primeiro elemento, o último, o do meio e uma escolha aleatória. Assim, vamos ver como cada escolha impacta o desempenho do algoritmo.
Passo 2
Primeiro, vamos implementar o Quicksort onde o pivô é sempre o primeiro elemento da lista. O Quicksort é um algoritmo de ordenação que funciona dividindo a lista em duas partes com base no pivô: os menores que o pivô ficam à esquerda e os maiores à direita. Depois, ele ordena essas partes recursivamente.
def quicksort_first_pivot(arr):
if len(arr) <= 1:
return arr
pivot = arr[0] # Pivô é o primeiro elemento
menores = [x for x in arr[1:] if x < pivot]
maiores = [x for x in arr[1:] if x >= pivot]
return quicksort_first_pivot(menores) + [pivot] + quicksort_first_pivot(maiores)
Passo 3
Agora, vamos modificar o Quicksort para escolher o último elemento como pivô. A lógica é a mesma, só muda a posição do pivô.
def quicksort_last_pivot(arr):
if len(arr) <= 1:
return arr
pivot = arr[-1] # Pivô é o último elemento
menores = [x for x in arr[:-1] if x < pivot]
maiores = [x for x in arr[:-1] if x >= pivot]
return quicksort_last_pivot(menores) + [pivot] + quicksort_last_pivot(maiores)
Passo 4
Vamos implementar agora o Quicksort com o pivô sendo o elemento do meio da lista. Isso pode ajudar a balancear melhor as divisões.
def quicksort_middle_pivot(arr):
if len(arr) <= 1:
return arr
meio = len(arr) // 2
pivot = arr[meio] # Pivô é o elemento do meio
menores = [x for x in arr[:meio] + arr[meio+1:] if x < pivot]
maiores = [x for x in arr[:meio] + arr[meio+1:] if x >= pivot]
return quicksort_middle_pivot(menores) + [pivot] + quicksort_middle_pivot(maiores)
Passo 5
Por fim, vamos criar uma versão onde o pivô é escolhido de forma aleatória. Isso pode ajudar a evitar o pior caso em listas que já estão quase ordenadas.
import random
def quicksort_random_pivot(arr):
if len(arr) <= 1:
return arr
meio = random.randint(0, len(arr) - 1)
pivot = arr[meio] # Pivô é um elemento aleatório
menores = [x for x in arr[:meio] + arr[meio+1:] if x < pivot]
maiores = [x for x in arr[:meio] + arr[meio+1:] if x >= pivot]
return quicksort_random_pivot(menores) + [pivot] + quicksort_random_pivot(maiores)
Passo 6
Agora que temos as quatro versões do Quicksort, vamos analisar o impacto da escolha do pivô no tempo de execução:
-
Pivô como o primeiro elemento: Se a lista já estiver ordenada ou quase ordenada, isso pode levar a um tempo de execução $ O(n^2) $, porque as divisões serão muito desbalanceadas.
-
Pivô como o último elemento: Similar ao primeiro pivô, também pode causar $ O(n^2) $ no pior caso se a lista estiver ordenada.
-
Pivô como o elemento do meio: Geralmente melhora a divisão das listas, levando a tempos próximos de $ O(n \log n) $, mas ainda pode ser afetado em casos específicos.
-
Pivô aleatório: Aumenta a chance de ter divisões balanceadas, geralmente alcançando $ O(n \log n) $ de forma mais consistente, independentemente da ordem inicial da lista.
Ou seja, a escolha do pivô é crucial para o desempenho do Quicksort. Pivôs que tendem a dividir a lista de forma equilibrada levam a uma melhor performance, enquanto escolhas desbalanceadas podem degradar o tempo de execução significativamente.
Resposta
Implementamos o Quicksort com quatro estratégias diferentes de escolha de pivô e observamos que escolher o pivô aleatoriamente ou como o elemento do meio geralmente proporciona um desempenho melhor e mais consistente, mantendo o tempo de execução próximo a $ O(n \log n) $. Já escolher sempre o primeiro ou o último elemento como pivô pode levar a um tempo de execução de $ O(n^2) $ em casos desfavoráveis, como listas já ordenadas.