Quick Sort e Seleção do Pivô
Crie o quick sort com os esquemas de partição de Lomuto e Hoare, analise o pior caso O(n²) e veja como a seleção aleatória do pivô o reduz.
Quick Sort e Seleção do Pivô é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Ordenação rápida: dividir para conquistar no próprio vetor
A ordenação rápida é o algoritmo de ordenação mais usado na prática. Ao contrário da ordenação por intercalação, ela ordena no próprio vetor sem alocar vetores adicionais. A ideia central é escolher um elemento pivô, particionar o vetor para que todos os elementos menores que o pivô fiquem antes dele e todos os elementos maiores fiquem depois dele e, então, ordenar recursivamente cada partição. A etapa de particionamento leva O(n) tempo e, com um bom pivô, a profundidade da recursão é O(log n).
def quick_sort(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
pivot_idx = partition(arr, lo, hi)
quick_sort(arr, lo, pivot_idx - 1) # sort left
quick_sort(arr, pivot_idx + 1, hi) # sort right
def partition(arr, lo, hi):
pivot = arr[hi] # Lomuto: choose last element as pivot
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]Esquema de particionamento de Lomuto
O particionamento de Lomuto usa o último elemento como pivô. Um ponteiro lento i acompanha o limite da região de elementos “menores que o pivô”; um ponteiro rápido j percorre o vetor para a frente. Quando arr[j] <= pivot, incremente i e troque arr[i] por arr[j], ampliando a região de elementos menores. Depois da varredura, coloque o pivô em i+1, trocando-o por arr[hi]. É simples de implementar, mas realiza 3 vezes mais trocas que o esquema de Hoare.
def lomuto_partition_traced(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
print(f'Pivot: {pivot}, array: {arr[lo:hi+1]}')
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
print(f'After partition: {arr[lo:hi+1]}')
return i + 1
arr = [3, 1, 4, 1, 5, 9, 2, 6]
lomuto_partition_traced(arr, 0, len(arr)-1)Esquema de particionamento de Hoare
O particionamento de Hoare usa dois ponteiros que começam nas duas extremidades e avançam para o centro até se cruzarem. Ele escolhe o pivô (geralmente o primeiro elemento) e move os elementos menores que o pivô para a esquerda e os maiores para a direita. O esquema de Hoare realiza 3 vezes menos trocas que o de Lomuto e funciona melhor com elementos iguais, mas o pivô não termina em sua posição final após o particionamento — o que exige chamadas recursivas ligeiramente diferentes.
def hoare_partition(arr, lo, hi):
pivot = arr[lo] # first element as pivot
i, j = lo - 1, hi + 1
while True:
i += 1
while arr[i] < pivot: i += 1
j -= 1
while arr[j] > pivot: j -= 1
if i >= j: return j
arr[i], arr[j] = arr[j], arr[i]
def quick_sort_hoare(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
p = hoare_partition(arr, lo, hi)
quick_sort_hoare(arr, lo, p) # note: p not p-1
quick_sort_hoare(arr, p+1, hi)
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort_hoare(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]Pior caso O(n²): entrada já ordenada
O pior caso da ordenação rápida ocorre quando o pivô é sempre o menor ou o maior elemento da partição. Com o pivô no último elemento do particionamento de Lomuto em um vetor já ordenado, o particionamento sempre coloca 0 elementos à esquerda e n-1 à direita: a árvore de recursão se degenera em uma cadeia de profundidade n, produzindo O(n²) comparações. Por isso, a seleção do pivô é fundamental e as implementações de produção escolhem o pivô de forma aleatória.
import sys
sys.setrecursionlimit(5000)
def quick_sort_naive(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
comparisons = [0]
def _qs(lo, hi):
if lo >= hi: return
pivot = arr[hi] # last element pivot
i = lo - 1
for j in range(lo, hi):
comparisons[0] += 1
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
_qs(lo, p-1); _qs(p+1, hi)
_qs(lo, hi)
return comparisons[0]
import math
n = 100
sorted_arr = list(range(n))
ops = quick_sort_naive(sorted_arr)
print(f'n={n}, ops={ops}, n^2={n**2}') # ops close to n*(n-1)/2Pivô aleatório: O(n log n) esperado
Ao escolher o pivô uniformemente ao acaso (troque um elemento aleatório por arr[hi] antes do particionamento), a probabilidade de escolher consistentemente pivôs ruins diminui exponencialmente. O número esperado de comparações é 2n ln(n) ≈ 1,39 n log₂(n), resultando em tempo esperado O(n log n) com probabilidade esmagadora. É por isso que a ordenação rápida aleatória é usada na prática — ela evita piores casos patológicos que um adversário poderia criar para estratégias com pivô fixo.
import random
def quick_sort_random(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
# Randomise pivot
rand_i = random.randint(lo, hi)
arr[rand_i], arr[hi] = arr[hi], arr[rand_i]
# Lomuto partition with last element as pivot
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
quick_sort_random(arr, lo, p - 1)
quick_sort_random(arr, p + 1, hi)
arr = list(range(100, 0, -1)) # worst case for naive
quick_sort_random(arr)
print(arr[:10]) # [1,2,3,4,5,6,7,8,9,10]Pivô pela mediana de três
Outra estratégia de escolha do pivô é escolher a mediana do primeiro, do elemento central e do último elemento. Isso evita o comportamento de pior caso em entradas ordenadas ou ordenadas em ordem inversa (as entradas adversariais mais comuns), sem o custo da geração de números aleatórios. Muitas implementações de produção usam a mediana de três ou a mediana de três medianas para vetores grandes e recorrem à ordenação por inserção para subvetores pequenos, abaixo de um limite de aproximadamente 10 elementos.
def median_of_three(arr, lo, hi):
mid = (lo + hi) // 2
# Sort lo, mid, hi values in place
if arr[lo] > arr[mid]: arr[lo], arr[mid] = arr[mid], arr[lo]
if arr[lo] > arr[hi]: arr[lo], arr[hi] = arr[hi], arr[lo]
if arr[mid] > arr[hi]: arr[mid], arr[hi] = arr[hi], arr[mid]
# Median is now at arr[mid]; swap to arr[hi-1] as pivot
arr[mid], arr[hi] = arr[hi], arr[mid]
return arr[hi] # pivot value
arr = [3, 9, 1]
print(median_of_three(arr, 0, 2), arr) # 3, [1,3,9] (sorted)Bandeira nacional holandesa: particionamento em três vias
O particionamento padrão coloca os elementos menores que o pivô à esquerda e os maiores à direita, mas os elementos iguais ao pivô ficam espalhados. O particionamento em três vias (bandeira nacional holandesa) cria três regiões: <pivô, ==pivô, >pivô. Isso é fundamental para vetores com muitas duplicatas — neles, a ordenação rápida padrão se degrada para O(n²), mas a ordenação rápida em três vias produz O(n) para entradas cujos valores são todos iguais.
def three_way_partition(arr, lo, hi):
pivot = arr[lo]
lt = lo # arr[lo..lt-1] < pivot
gt = hi # arr[gt+1..hi] > pivot
i = lo # current
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1; i += 1
elif arr[i] > pivot:
arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1 # don't advance i
else:
i += 1
return lt, gt # pivot occupies arr[lt..gt]
arr = [3, 1, 4, 1, 5, 9, 2, 6, 3, 3]
lt, gt = three_way_partition(arr, 0, len(arr)-1)
print(arr, '| pivot region:', lt, 'to', gt)quickselect: k-ésimo menor em O(n)
quickselect usa a etapa de particionamento da ordenação rápida para encontrar o k-ésimo menor elemento em tempo médio O(n), sem ordenar completamente. Depois do particionamento, o pivô está em sua posição final p. Se p == k, retorne arr[p]. Se k < p, recorra à partição esquerda; se k > p, recorra à partição direita. Em média, cada recursão reduz o problema pela metade: O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n).
import random
def quickselect(nums, k):
'''Find kth smallest (0-indexed) in O(n) average.'''
def _select(lo, hi):
if lo == hi: return nums[lo]
rand_i = random.randint(lo, hi)
nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
pivot = nums[hi]
i = lo - 1
for j in range(lo, hi):
if nums[j] <= pivot:
i += 1; nums[i], nums[j] = nums[j], nums[i]
p = i + 1
nums[p], nums[hi] = nums[hi], nums[p]
if p == k: return nums[p]
elif k < p: return _select(lo, p - 1)
else: return _select(p + 1, hi)
return _select(0, len(nums) - 1)
print(quickselect([3,2,1,5,6,4], 1)) # 2 (2nd smallest)Complexidade de espaço da ordenação rápida
A ordenação rápida é chamada de “no próprio vetor”, mas usa espaço médio O(log n) na pilha para a recursão (um quadro por nível da árvore de recursão). No pior caso, a profundidade da pilha é O(n). Para garantir espaço O(log n) na pilha no pior caso, sempre faça a recursão primeiro na partição menor e use otimização de chamada de cauda para a partição maior. O limite de recursão do Python torna arriscadas as recursões muito profundas da ordenação rápida — vale mencionar isso em entrevistas.
def quick_sort_optimised(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
while lo < hi:
p = lomuto_partition_qs(arr, lo, hi)
# Recurse on smaller partition; iterate on larger
if p - lo < hi - p:
quick_sort_optimised(arr, lo, p - 1)
lo = p + 1 # tail-call elimination
else:
quick_sort_optimised(arr, p + 1, hi)
hi = p - 1
def lomuto_partition_qs(arr, lo, hi):
pivot = arr[hi]; i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot: i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1Comparação entre algoritmos de ordenação
Sintetize seu conhecimento:
- Ordenação rápida: O(n log n) esperado, O(n²) no pior caso, espaço O(log n), não estável, mais rápida na prática para dados aleatórios
- Ordenação por intercalação: O(n log n) garantido, espaço O(n), estável, melhor para listas encadeadas e ordenação externa
- Ordenação por montículo: O(n log n) garantido, espaço O(1), não estável, mais lenta na prática devido às falhas de cache
- Ordenação por inserção: caso melhor O(n), ideal para n pequeno ou dados quase ordenados
# Python's sorted() uses Timsort:
# - Hybrid: merge sort for large runs, insertion sort for small (< 64 elements)
# - Stable, O(n log n) worst case
# - O(n) best case for sorted/reverse-sorted/nearly-sorted
# - O(n) extra space
import random
arr = random.sample(range(10000), 1000)
sorted_arr = sorted(arr) # Timsort
print(sorted_arr[:5], '...') # first 5 elementsIntrosort: combinando os três
Introsort (usado no STL do C++ std::sort) combina ordenação rápida, ordenação por montículo e ordenação por inserção: começa com uma ordenação rápida aleatória; se a profundidade da recursão exceder 2 log n (indicando uma sequência de pivôs ruins), muda para a ordenação por montículo para garantir O(n log n); usa ordenação por inserção para subvetores menores que 16 elementos. Isso produz pior caso O(n log n), com a velocidade média da ordenação rápida e a eficiência da ordenação por inserção para subvetores pequenos.
# Introsort hybrid (simplified)
def introsort(arr, depth_limit=None):
if depth_limit is None:
import math
depth_limit = 2 * int(math.log2(len(arr) + 1)) if arr else 0
if len(arr) <= 16:
# insertion sort for small arrays
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1
arr[j+1] = key
return arr
if depth_limit == 0:
arr.sort() # fall back to heapsort equivalent
return arr
# Otherwise quick sort
pivot = arr[-1]
small = [x for x in arr[:-1] if x <= pivot]
large = [x for x in arr[:-1] if x > pivot]
return introsort(small, depth_limit-1) + [pivot] + introsort(large, depth_limit-1)
print(introsort([5,3,8,1,9,2,7]))Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu que: a ordenação rápida particiona o vetor no próprio vetor em torno de um pivô e faz recursão em cada lado, alcançando tempo esperado O(n log n) com espaço O(log n) na pilha — mais rápida na prática que a ordenação por intercalação para dados aleatórios; o pior caso O(n²) ocorre em entradas ordenadas com um pivô fixo e é evitado pela seleção aleatória do pivô ou pela mediana de três; e o particionamento em três vias lida eficientemente com elementos duplicados, enquanto quickselect amplia a ideia de particionamento para encontrar o k-ésimo menor elemento em tempo médio O(n), sem uma ordenação completa. Em seguida, exploraremos ordenações que não usam comparações e a ordenação integrada ao Python.
Perguntas Frequentes
A aula “Quick Sort e Seleção do Pivô” é grátis?
Sim — o texto completo de “Quick Sort e Seleção do Pivô” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Quick Sort e Seleção do Pivô”?
Crie o quick sort com os esquemas de partição de Lomuto e Hoare, analise o pior caso O(n²) e veja como a seleção aleatória do pivô o reduz. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Quick Sort e Seleção do Pivô”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Ordenação por Bolhas e por Inserção
- Ordenação por Intercalação: Dividir, Ordenar, Intercalar
- Quick Sort e Seleção do Pivô
- Ordenações sem Comparação e o sort() do Python