Quicksort é um algoritmo de ordenação dividir-e-conquistar que escolhe um pivô, particiona elementos em menores e maiores que ele, e depois ordena recursivamente cada lado. Média O(n log n), pior caso O(n²).
Particionamento coloca o pivô em sua posição final ordenada; tudo à esquerda é menor, tudo à direita é maior. Repita recursivamente em ambos os lados.
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # pick a pivot
left = [x for x in arr if x < pivot] # smaller
mid = [x for x in arr if x == pivot] # equal
right = [x for x in arr if x > pivot] # larger
return quicksort(left) + mid + quicksort(right)
quicksort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8]
(O particionamento in-place é usado na prática para economizar memória.)
| Caso | Tempo | Causa |
|---|---|---|
| Melhor/Médio | O(n log n) | partições balanceadas |
| Pior | O(n²) | já ordenado com pivô ruim |
Quicksort in-place usa O(log n) de espaço de pilha.
Usualmente o mais rápido na prática devido à amigabilidade com cache e baixa sobrecarga, e é in-place. O pior caso O(n²) é evitado com um pivô aleatorizado ou mediana-de-três. Não é estável.
Quicksort é o padrão em muitas bibliotecas porque tem excelente velocidade de caso médio e baixo uso de memória.
Entender por que a escolha do pivô causa o pior caso O(n²) ensina uma lição-chave: caso médio e pior caso podem divergir drasticamente.
É um tópico favorito de entrevista precisamente por causa dessa nuance.