Quick Sort: Como Funciona, Animação e Código em C, Python e Java

O Quick Sort escolhe um elemento chamado pivô e reorganiza o vetor de modo que os menores fiquem à esquerda dele e os maiores à direita. O pivô então está na posição final, e o processo se repete recursivamente em cada lado.

Como o Quick Sort Funciona

Escolha um pivô (nesta animação, o último elemento do trecho).
Percorra o trecho levando para a esquerda todos os elementos menores que o pivô (particionamento).
Coloque o pivô logo depois do último elemento menor: essa é sua posição definitiva.
Aplique o Quick Sort no trecho à esquerda e no trecho à direita do pivô.
Trechos com 0 ou 1 elemento já estão ordenados.

Complexidade do Quick Sort

Melhor caso	Caso médio	Pior caso	Memória extra	Estável?
O(n log n)	O(n log n)	O(n²)	O(log n)	Não

Quando usar

É o algoritmo de uso geral mais rápido na prática para dados em memória, por ter ótima localidade de cache. Implementações reais escolhem o pivô de forma aleatória ou pela mediana de três para evitar o pior caso.

Quick Sort em C

int particionar(int v[], int lo, int hi) {
    int pivo = v[hi], i = lo;
    for (int j = lo; j < hi; j++) {
        if (v[j] < pivo) {
            int aux = v[i]; v[i] = v[j]; v[j] = aux;
            i++;
        }
    }
    int aux = v[i]; v[i] = v[hi]; v[hi] = aux;
    return i;
}

void quick_sort(int v[], int lo, int hi) {
    if (lo < hi) {
        int p = particionar(v, lo, hi);
        quick_sort(v, lo, p - 1);
        quick_sort(v, p + 1, hi);
    }
}

Quick Sort em Python

def quick_sort(v, lo=0, hi=None):
    if hi is None:
        hi = len(v) - 1
    if lo < hi:
        pivo, i = v[hi], lo
        for j in range(lo, hi):
            if v[j] < pivo:
                v[i], v[j] = v[j], v[i]
                i += 1
        v[i], v[hi] = v[hi], v[i]
        quick_sort(v, lo, i - 1)
        quick_sort(v, i + 1, hi)
    return v

Quick Sort em Java

static void quickSort(int[] v, int lo, int hi) {
    if (lo >= hi) return;
    int pivo = v[hi], i = lo;
    for (int j = lo; j < hi; j++) {
        if (v[j] < pivo) {
            int aux = v[i]; v[i] = v[j]; v[j] = aux;
            i++;
        }
    }
    int aux = v[i]; v[i] = v[hi]; v[hi] = aux;
    quickSort(v, lo, i - 1);
    quickSort(v, i + 1, hi);
}

Quer comparar com outros métodos? No visualizador de algoritmos de ordenação você roda todos no mesmo vetor e compara o número de comparações e trocas.

Perguntas Frequentes

Qual a complexidade do Quick Sort?

O(n log n) no melhor caso e no caso médio. No pior caso, quando o pivô é sempre o menor ou o maior elemento (por exemplo, vetor já ordenado com pivô no fim), cai para O(n²).

Como evitar o pior caso do Quick Sort?

Escolhendo o pivô aleatoriamente ou pela mediana de três (primeiro, meio e último). Algumas bibliotecas trocam para Heap Sort quando a recursão fica profunda demais (Introsort).

O Quick Sort é estável?

Não. O particionamento troca elementos distantes, o que pode inverter a ordem de elementos iguais.

Quick Sort: Animação Passo a Passo