Equipe Rust Brasil 12 min de leitura

Quick Sort em Rust

Aprenda Quick Sort em Rust com particionamento Lomuto e Hoare, mediana de três, diagramas visuais e análise Big-O completa.

ordenação quick-sort algoritmos rust divisão-e-conquista

O Quick Sort (ordenação rápida) é um dos algoritmos de ordenação mais utilizados na prática. Inventado por Tony Hoare em 1959, ele utiliza a estratégia de divisão e conquista: escolhe um elemento como pivô, particiona o vetor de modo que todos os menores fiquem à esquerda e os maiores à direita, e então ordena recursivamente cada partição.

O Quick Sort é o algoritmo padrão em muitas implementações de bibliotecas de ordenação — incluindo a função sort_unstable() do Rust — por ser extremamente eficiente na prática: seu desempenho médio é O(n log n) com constantes muito pequenas, e por ser in-place, usa apenas O(log n) de memória extra para a pilha de recursão. Sua principal fraqueza é o pior caso O(n²), que pode ser evitado com boas estratégias de escolha do pivô.

Como Funciona

O algoritmo segue três passos:

  1. Escolher pivô: selecionar um elemento do vetor como referência.
  2. Particionar: reorganizar o vetor para que elementos menores que o pivô fiquem à esquerda e maiores à direita.
  3. Recursar: aplicar Quick Sort nas duas partições.
Vetor inicial: [8, 3, 7, 1, 5, 2, 9, 4, 6]
                                         ^
                                       pivô = 6

=== PARTICIONAMENTO ===
Objetivo: colocar todos os < 6 à esquerda e todos os > 6 à direita

[8, 3, 7, 1, 5, 2, 9, 4, 6]
 i→                       pivô

Passo 1: 8 > 6 → não move i
Passo 2: 3 < 6 → troca com posição i → [3, 8, 7, 1, 5, 2, 9, 4, 6], i avança
Passo 3: 7 > 6 → não move i
Passo 4: 1 < 6 → troca → [3, 1, 7, 8, 5, 2, 9, 4, 6], i avança
Passo 5: 5 < 6 → troca → [3, 1, 5, 8, 7, 2, 9, 4, 6], i avança
Passo 6: 2 < 6 → troca → [3, 1, 5, 2, 7, 8, 9, 4, 6], i avança
Passo 7: 9 > 6 → não move i
Passo 8: 4 < 6 → troca → [3, 1, 5, 2, 4, 8, 9, 7, 6], i avança
Colocar pivô na posição i: [3, 1, 5, 2, 4, 6, 9, 7, 8]
                            |--- < 6 ---|  ^  |-- > 6 -|
                                         pivô

=== RECURSÃO ===
Quick Sort([3, 1, 5, 2, 4])    Quick Sort([9, 7, 8])
         ↓                              ↓
   [1, 2, 3, 4, 5]                [7, 8, 9]

Resultado: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Complexidade

CasoTempoEspaço
MelhorO(n log n)O(log n)
MédioO(n log n)O(log n)
PiorO(n²)O(n)
  • Melhor caso O(n log n): quando o pivô sempre divide o vetor em duas metades iguais. Gera log n níveis de recursão com O(n) trabalho cada.
  • Caso médio O(n log n): mesmo com divisões desbalanceadas, desde que não sejam extremas, a complexidade permanece O(n log n). Análise probabilística mostra que pivôs aleatórios geram partições razoáveis na maioria das vezes.
  • Pior caso O(n²): ocorre quando o pivô é sempre o menor ou maior elemento (ex: vetor já ordenado com pivô no final). Cada partição remove apenas 1 elemento, gerando n níveis de recursão.
  • Espaço O(log n): a pilha de recursão tem profundidade log n no caso médio. No pior caso, pode chegar a O(n).

Implementação em Rust

Particionamento de Lomuto

/// Quick Sort com particionamento de Lomuto.
/// O pivô é o último elemento.
fn quick_sort_lomuto<T: PartialOrd>(vetor: &mut [T]) {
    let n = vetor.len();
    if n <= 1 {
        return;
    }

    let indice_pivo = particionar_lomuto(vetor);

    // Ordenar a parte esquerda (antes do pivô)
    quick_sort_lomuto(&mut vetor[..indice_pivo]);

    // Ordenar a parte direita (depois do pivô)
    if indice_pivo + 1 < n {
        quick_sort_lomuto(&mut vetor[indice_pivo + 1..]);
    }
}

/// Particionamento de Lomuto.
/// Escolhe o último elemento como pivô.
/// Retorna a posição final do pivô.
fn particionar_lomuto<T: PartialOrd>(vetor: &mut [T]) -> usize {
    let n = vetor.len();
    let pivo_idx = n - 1;
    let mut i = 0; // posição onde o próximo elemento menor será colocado

    for j in 0..pivo_idx {
        if vetor[j] <= vetor[pivo_idx] {
            vetor.swap(i, j);
            i += 1;
        }
    }

    // Colocar o pivô na posição correta
    vetor.swap(i, pivo_idx);
    i
}

fn main() {
    let mut v = vec![8, 3, 7, 1, 5, 2, 9, 4, 6];
    println!("Antes:  {:?}", v);
    quick_sort_lomuto(&mut v);
    println!("Depois: {:?}", v);
}

Particionamento de Hoare

O esquema de Hoare é mais eficiente que o de Lomuto, pois faz em média 3x menos trocas:

/// Quick Sort com particionamento de Hoare.
/// Geralmente mais eficiente que Lomuto.
fn quick_sort_hoare<T: PartialOrd + Clone>(vetor: &mut [T]) {
    let n = vetor.len();
    if n <= 1 {
        return;
    }
    quick_sort_hoare_interno(vetor, 0, n - 1);
}

fn quick_sort_hoare_interno<T: PartialOrd + Clone>(
    vetor: &mut [T],
    inicio: usize,
    fim: usize,
) {
    if inicio >= fim {
        return;
    }

    let p = particionar_hoare(vetor, inicio, fim);

    if p > 0 {
        quick_sort_hoare_interno(vetor, inicio, p);
    }
    quick_sort_hoare_interno(vetor, p + 1, fim);
}

/// Particionamento de Hoare.
/// Usa dois ponteiros que se movem de fora para dentro.
fn particionar_hoare<T: PartialOrd + Clone>(
    vetor: &mut [T],
    inicio: usize,
    fim: usize,
) -> usize {
    let pivo = vetor[inicio].clone();
    let mut i = inicio;
    let mut j = fim;

    loop {
        // Avançar i enquanto vetor[i] < pivô
        while vetor[i] < pivo {
            i += 1;
        }

        // Retroceder j enquanto vetor[j] > pivô
        while vetor[j] > pivo {
            j -= 1;
        }

        if i >= j {
            return j;
        }

        vetor.swap(i, j);
        i += 1;
        j -= 1;
    }
}

fn main() {
    let mut v = vec![8, 3, 7, 1, 5, 2, 9, 4, 6];
    println!("Antes:  {:?}", v);
    quick_sort_hoare(&mut v);
    println!("Depois: {:?}", v);
}

Exemplo de Execução

Antes:  [8, 3, 7, 1, 5, 2, 9, 4, 6]
Depois: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Rastreamento do particionamento de Lomuto com o vetor [8, 3, 7, 1, 5]:

Pivô = 5 (último elemento)
i = 0

j=0: vetor[0]=8 > 5 → nada          [8, 3, 7, 1, 5]  i=0
j=1: vetor[1]=3 ≤ 5 → swap(0,1)     [3, 8, 7, 1, 5]  i=1
j=2: vetor[2]=7 > 5 → nada          [3, 8, 7, 1, 5]  i=1
j=3: vetor[3]=1 ≤ 5 → swap(1,3)     [3, 1, 7, 8, 5]  i=2

Colocar pivô: swap(2, 4)            [3, 1, 5, 8, 7]
                                      ←<5→  ^  ←>5→
                                           pivô na posição 2

Variações e Otimizações

1. Mediana de Três

Escolher o pivô como a mediana de três elementos (primeiro, meio e último) evita o pior caso em vetores já ordenados ou quase ordenados:

/// Quick Sort com mediana de três para escolha do pivô.
fn quick_sort_mediana<T: PartialOrd>(vetor: &mut [T]) {
    let n = vetor.len();
    if n <= 1 {
        return;
    }

    // Otimização: Insertion Sort para partições pequenas
    if n <= 16 {
        for i in 1..n {
            let mut j = i;
            while j > 0 && vetor[j - 1] > vetor[j] {
                vetor.swap(j - 1, j);
                j -= 1;
            }
        }
        return;
    }

    // Mediana de três: organizar primeiro, meio e último
    let meio = n / 2;
    let ultimo = n - 1;

    // Colocar a mediana na posição do meio
    if vetor[0] > vetor[meio] {
        vetor.swap(0, meio);
    }
    if vetor[0] > vetor[ultimo] {
        vetor.swap(0, ultimo);
    }
    if vetor[meio] > vetor[ultimo] {
        vetor.swap(meio, ultimo);
    }

    // Mover o pivô (mediana) para a penúltima posição
    vetor.swap(meio, ultimo - 1);

    // Particionar usando o pivô na posição ultimo-1
    let mut i = 0;
    let mut j = ultimo - 1;
    let pivo_pos = ultimo - 1;

    loop {
        i += 1;
        while vetor[i] < vetor[pivo_pos] {
            i += 1;
        }
        j -= 1;
        while vetor[j] > vetor[pivo_pos] {
            if j == 0 {
                break;
            }
            j -= 1;
        }
        if i >= j {
            break;
        }
        vetor.swap(i, j);
    }

    // Restaurar o pivô
    vetor.swap(i, pivo_pos);

    // Recursão nas duas partições
    quick_sort_mediana(&mut vetor[..i]);
    if i + 1 < n {
        quick_sort_mediana(&mut vetor[i + 1..]);
    }
}

fn main() {
    let mut v = vec![8, 3, 7, 1, 5, 2, 9, 4, 6];
    println!("Antes:  {:?}", v);
    quick_sort_mediana(&mut v);
    println!("Depois: {:?}", v);

    // Caso que seria pior caso sem mediana de três
    let mut ordenado = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    quick_sort_mediana(&mut ordenado);
    println!("Já ordenado: {:?}", ordenado);
}

2. Particionamento de Três Vias (Dutch National Flag)

Quando há muitos elementos duplicados, o particionamento de três vias (menor, igual, maior) é significativamente mais eficiente:

/// Quick Sort com particionamento de três vias.
/// Eficiente quando há muitos elementos duplicados.
fn quick_sort_tres_vias<T: PartialOrd + Clone>(vetor: &mut [T]) {
    let n = vetor.len();
    if n <= 1 {
        return;
    }
    quick_sort_tres_vias_interno(vetor, 0, n - 1);
}

fn quick_sort_tres_vias_interno<T: PartialOrd + Clone>(
    vetor: &mut [T],
    inicio: usize,
    fim: usize,
) {
    if inicio >= fim {
        return;
    }

    let pivo = vetor[inicio].clone();
    let mut menor = inicio;   // vetor[inicio..menor] < pivô
    let mut atual = inicio;    // vetor[menor..atual] == pivô
    let mut maior = fim;       // vetor[maior+1..fim] > pivô

    while atual <= maior {
        if vetor[atual] < pivo {
            vetor.swap(menor, atual);
            menor += 1;
            atual += 1;
        } else if vetor[atual] > pivo {
            vetor.swap(atual, maior);
            if maior == 0 {
                break;
            }
            maior -= 1;
            // Não incrementa atual — o elemento trocado precisa ser verificado
        } else {
            atual += 1;
        }
    }

    // Recursão: pular todos os iguais ao pivô
    if menor > 0 {
        quick_sort_tres_vias_interno(vetor, inicio, menor - 1);
    }
    if maior < fim {
        quick_sort_tres_vias_interno(vetor, maior + 1, fim);
    }
}

fn main() {
    // Vetor com muitos duplicados
    let mut v = vec![3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 1, 3];
    println!("Antes:  {:?}", v);
    quick_sort_tres_vias(&mut v);
    println!("Depois: {:?}", v);
}

Visualização do particionamento de três vias:

Pivô = 5     [5, 3, 8, 5, 2, 5, 9, 1]

              [5, 3, 8, 5, 2, 5, 9, 1]
               m  a                 M

atual=5: == pivô → avança
              [5, 3, 8, 5, 2, 5, 9, 1]    m=0, a=1, M=7

atual=3: < pivô → swap(menor, atual), avança ambos
              [3, 5, 8, 5, 2, 5, 9, 1]    m=1, a=2, M=7

atual=8: > pivô → swap(atual, maior)
              [3, 5, 1, 5, 2, 5, 9, 8]    m=1, a=2, M=6

... continua até atual > maior ...

Resultado:    [< 5 ... | 5, 5, 5 | ... > 5]
               ← menor  ← iguais →  maior →

3. Tail-Call Optimization

Para evitar estouro de pilha, podemos aplicar recursão apenas na partição menor e iterar na maior:

/// Quick Sort com otimização de tail-call.
/// Garante profundidade de recursão O(log n).
fn quick_sort_tail<T: PartialOrd>(vetor: &mut [T]) {
    let mut inicio = 0;
    let mut fim = vetor.len();

    while fim - inicio > 1 {
        // Particionar
        let pivo_idx = {
            let n = fim - inicio;
            let pivo_pos = fim - 1;
            let mut i = inicio;

            for j in inicio..pivo_pos {
                if vetor[j] <= vetor[pivo_pos] {
                    vetor.swap(i, j);
                    i += 1;
                }
            }
            vetor.swap(i, pivo_pos);
            i
        };

        // Recursão na partição menor, iteração na maior
        let tamanho_esquerda = pivo_idx - inicio;
        let tamanho_direita = fim - pivo_idx - 1;

        if tamanho_esquerda < tamanho_direita {
            quick_sort_tail(&mut vetor[inicio..pivo_idx]);
            inicio = pivo_idx + 1; // iterar na parte direita
        } else {
            if pivo_idx + 1 < fim {
                quick_sort_tail(&mut vetor[pivo_idx + 1..fim]);
            }
            fim = pivo_idx; // iterar na parte esquerda
        }
    }
}

fn main() {
    let mut v = vec![8, 3, 7, 1, 5, 2, 9, 4, 6];
    println!("Antes:  {:?}", v);
    quick_sort_tail(&mut v);
    println!("Depois: {:?}", v);
}

Quando Usar

O Quick Sort é a escolha adequada nos seguintes cenários:

  • Uso geral: é o algoritmo de ordenação mais rápido na prática para a maioria dos conjuntos de dados em memória, graças ao excelente padrão de acesso ao cache.
  • Memória limitada: por ser in-place (O(log n) de espaço extra), é preferível ao Merge Sort quando memória é restrita.
  • Estabilidade não necessária: o Quick Sort padrão é instável. Se estabilidade for necessária, use Merge Sort.
  • Muitos duplicados: com particionamento de três vias, o Quick Sort lida eficientemente com chaves repetidas.
  • Dados em memória (não em disco): o Quick Sort se beneficia do acesso sequencial à memória.

Evite o Quick Sort quando:

  • Garantia de O(n log n) for obrigatória no pior caso — use Merge Sort ou Heap Sort.
  • Os dados estiverem em disco — o Merge Sort é melhor para ordenação externa.
  • Estabilidade for necessária — use Merge Sort ou o sort() estável do Rust.

Comparação com Outros Algoritmos

CaracterísticaQuick SortMerge SortHeap SortInsertion Sort
Tempo (médio)O(n log n)O(n log n)O(n log n)O(n²)
Tempo (pior)O(n²)O(n log n) ✓O(n log n) ✓O(n²)
EspaçoO(log n)O(n)O(1) ✓O(1) ✓
EstávelNãoSim ✓NãoSim ✓
Cache-friendlySim ✓NãoNãoSim ✓
In-placeSim ✓NãoSim ✓Sim ✓
Velocidade realMais rápido ✓BomMais lentoBom (n pequeno)

O Quick Sort é geralmente 2-3x mais rápido que o Merge Sort e Heap Sort na prática, mesmo compartilhando a mesma complexidade assintótica. Isso se deve ao melhor padrão de acesso ao cache e menor overhead por operação. A função sort_unstable() do Rust usa uma variante do Quick Sort (pattern-defeating quicksort) que combina o melhor de vários algoritmos.

Exercícios Práticos

  1. Quickselect: Implemente o algoritmo Quickselect para encontrar o k-ésimo menor elemento em tempo esperado O(n). Use o particionamento do Quick Sort mas recurse apenas no lado que contém a posição k.

  2. Quick Sort com pivô aleatório: Use uma seed fixa e uma função de hash simples (sem crates externas) para selecionar pivôs pseudo-aleatórios. Compare o desempenho com pivô fixo em vetores já ordenados.

  3. Análise de profundidade: Modifique o Quick Sort para rastrear a profundidade máxima de recursão. Teste com vetores aleatórios, ordenados e com muitos duplicados. Quais cenários geram a maior profundidade?

  4. Introsort simplificado: Implemente um Quick Sort que monitora a profundidade de recursão e, se ultrapassar 2 * log2(n), muda para Heap Sort. Esta é a ideia básica do Introsort, usado em C++.

Veja Também