QuickSort

O QuickSort particiona um intervalo ao redor de um pivô e ordena as partições recursivamente. Muitas vezes é rápido e econômico em memória, mas exige cuidado com pivôs, valores duplicados e profundidade da pilha.

static void quickSort(int[] values) {
    quickSort(values, 0, values.length - 1);
}

private static void quickSort(int[] values, int low, int high) {
    while (low < high) {
        int pivot = partition(values, low, high);
        if (pivot - low < high - pivot) {
            quickSort(values, low, pivot - 1);
            low = pivot + 1;
        } else {
            quickSort(values, pivot + 1, high);
            high = pivot - 1;
        }
    }
}

private static int partition(int[] values, int low, int high) {
    int pivotValue = values[high];
    int boundary = low;
    for (int scan = low; scan < high; scan++) {
        if (values[scan] <= pivotValue) swap(values, boundary++, scan);
    }
    swap(values, boundary, high);
    return boundary;
}

private static void swap(int[] values, int first, int second) {
    int temporary = values[first];
    values[first] = values[second];
    values[second] = temporary;
}

O exemplo escolhe o último valor como pivô para facilitar a compreensão. Durante o particionamento, os valores anteriores a boundary são menores ou iguais ao pivô, e os valores já examinados depois dele são maiores. Posicionar o pivô em boundary estabelece sua posição final; a indução prova o resultado recursivo.

Partições balanceadas custam Θ(n log n). A escolha aleatória do pivô tem tempo esperado Θ(n log n), não uma garantia absoluta; pivôs consistentemente extremos custam Θ(n²). O particionamento usa armazenamento Θ(1), e fazer a recursão apenas no lado menor limita a profundidade da pilha a O(log n). O algoritmo não é estável. O particionamento em três vias é preferível quando muitas chaves são iguais ao pivô.