Quick Sort

Definição

O Quick Sort é um algoritmo de ordenação baseado na técnica de dividir e conquistar (divide and conquer). Ele seleciona um elemento como pivô e particiona os demais elementos em dois subconjuntos:

Um com valores menores ou iguais ao pivô;
Outro com valores maiores.

Depois, o algoritmo aplica recursivamente o mesmo processo em cada subconjunto.

Por que usar

Muito eficiente na prática, mesmo para grandes volumes de dados;
Um dos algoritmos de ordenação mais utilizados;
Não requer muita memória adicional na versão in-place.

Complexidade

Caso	Tempo
Melhor caso	O(n log n)
Médio caso	O(n log n)
Pior caso	O(n²)

Estável? Não (a menos que adaptado)
Espaço adicional: O(log n) na média, por causa da pilha de chamadas recursivas

(Um algoritmo de ordenação é estável quando mantém a ordem original de elementos iguais após a ordenação.)

Exemplo prático (Python)

def quick_sort(lista):
    if len(lista) <= 1:
        return lista

    pivo = lista[0]
    menores = [x for x in lista[1:] if x <= pivo]
    maiores = [x for x in lista[1:] if x > pivo]

    return quick_sort(menores) + [pivo] + quick_sort(maiores)

numeros = [5, 3, 8, 1, 2]
ordenados = quick_sort(numeros)
print(ordenados)  # [1, 2, 3, 5, 8]

Visualização (divisão por pivô)

Dada a lista: [5, 3, 8, 1, 2]

Pivô: 5
Menores ou iguais: [3, 1, 2]
Maiores: [8]

Recursão em `[3, 1, 2]`:

Pivô: 3
- Menores: [1, 2]
- Maiores: []

Recursão em [1, 2]:

Pivô: 1
- Menores: []
- Maiores: [2]

Recursão em [8]:

Não há mais divisões — já está ordenado.

Reconstrução final:

[1, 2] + [3] + [] → [1, 2, 3]
[1, 2, 3] + [5] + [8] → [1, 2, 3, 5, 8]