Algoritmos em Python

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).

  • Intermediário
  • 2 min de leitura
  • 1 exemplo executável

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.

Das pilhas de livros ao código
pivot = values[len(values) // 2]📕 Escolha um livro para comparar
lower = [... if value < pivot]⬅️ Livros mais baixos para a esquerda
higher = [... if value > pivot]➡️ Livros mais altos para a direita
quick_sort(lower) + equal + quick_sort(higher)📚 Ordene cada lado e junte as pilhas
Particione em torno de um pivô e ordene cada lado do mesmo jeito.
Em uma frase

O 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

  1. if len(values) <= 1: é o caso base: uma lista assim já está ordenada.
  2. pivot = values[len(values) // 2] pega o valor do meio como pivô.
  3. lower, equal e higher separam os valores em torno do pivô; equal mantém os repetidos juntos.
  4. 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

Executar código →
main.py
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]))
Gerar um botão Run para este exemplo

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.

  1. Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
  2. Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
  3. Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Executar no compilador Python →

Erros comuns

Perder valores iguais ao pivô

Com só < e >, as cópias do pivô desaparecem.

Problema
return quick_sort(lower) + [pivot] + quick_sort(higher)
Correção
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