Ordenação rápida (quick sort) em Python
Nesta lição, você vai implementar o quick sort dividindo a lista em torno de um elemento pivô (pivot).
Introdução
O problema
O quicksort é uma das ideias de ordenação mais usadas, porque é rápido em média e fácil de expressar. Ele mostra outra forma de dividir um problema: em vez de dividir no meio, divida em torno de um valor escolhido.
Pense assim
O quicksort é como ordenar livros por altura em torno de um livro escolhido. Coloque todo livro mais baixo na pilha da esquerda, todo livro mais alto na pilha da direita e os da mesma altura no meio. Depois ordene cada pilha lateral do mesmo jeito e junte as pilhas.
pivot = values[len(values) // 2]📕 Escolha um livro para compararlower = [... if value < pivot]⬅️ Livros mais baixos para a esquerdahigher = [... if value > pivot]➡️ Livros mais altos para a direitaquick_sort(lower) + equal + quick_sort(higher)📚 Ordene cada lado e junte as pilhasO quicksort escolhe um pivô, separa os outros itens entre os menores e os maiores que ele, ordena cada parte recursivamente e as junta. Em média ele leva tempo O(n log n).
Pontos-chave
if len(values) <= 1:é o caso base: uma lista assim já está ordenada.pivot = values[len(values) // 2]pega o valor do meio como pivô.lower,equalehigherseparam os valores em torno do pivô;equalmantém os repetidos juntos.quick_sort(lower) + equal + quick_sort(higher)ordena os dois lados e junta as três listas.
Quando usar?
- Aprender particionamento e recursão.
- Ordenação de uso geral no próprio lugar (in-place), em linguagens e bibliotecas, com uma escolha cuidadosa do pivô.
- Problemas de seleção, como encontrar a mediana (o quickselect usa a mesma partição).
Quando não é preciso
- Código Python normal:
sorted()é mais rápido e estável. - Quando um pior caso garantido importa: com pivôs ruins, o quicksort vira
O(n²). O merge sort nunca chega a isso.
Visualizador de Ordenação rápida (quick sort) em Python
O(n log n)Use Executar ou Passo para acompanhar cada comparação e movimento dos dados.
Código de exemplo
def quick_sort(values):
if len(values) <= 1:
return values
pivot = values[len(values) // 2]
lower = [value for value in values if value < pivot]
equal = [value for value in values if value == pivot]
higher = [value for value in values if value > pivot]
return quick_sort(lower) + equal + quick_sort(higher)
print(quick_sort([10, 7, 8, 9, 1, 5]))
Resultado da execução
[1, 5, 7, 8, 9, 10]
Explicação do código
Esta versão, fácil de ler, escolhe o elemento do meio como pivô e cria três listas, lower, equal e higher, com list comprehension. O resultado é a junção de quick_sort(lower), equal e quick_sort(higher). A complexidade média é O(n log n), mas, se o pivô for mal escolhido, o algoritmo pode cair para O(n²).
Altere os valores e execute o programa no compilador Python online CodeUtility sem instalar Python.
Exercícios práticos
Tente modificar o código seguindo as sugestões abaixo. Mudar o código e observar o resultado ajuda você a entender muito mais do que só ler.
- Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
- Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
- Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Erros comuns
Perder valores iguais ao pivô
Com só < e >, as cópias do pivô desaparecem.
return quick_sort(lower) + [pivot] + quick_sort(higher)
return quick_sort(lower) + equal + quick_sort(higher)
Terminou esta lição?
Marque como aprendida para acompanhar seu progresso.
Pratique com um desafio
Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.
Todos os desafios