Quick Sort

Categoría: Sorting

El problema

El Merge Sort de este repositorio garantiza O(n log n) sin importar el orden de la entrada, pero paga esa garantía con un buffer auxiliar O(n). Lo que se necesita para un lote grande y con memoria ajustada es O(n log n) en el caso promedio in place — sin array auxiliar — aceptando un peor caso a cambio, siempre que ese peor caso pueda hacerse extremadamente improbable, en lugar de algo que una entrada real y no confiable pueda disparar a propósito o por accidente.

La solución

Elige un pivote, particiona el rango de modo que todo lo menor que él quede a la izquierda y todo lo mayor quede a la derecha — enteramente mediante intercambios dentro del array original, sin buffer auxiliar — y luego recurre en cada lado. El paso de partición es O(n); la profundidad promedio de recursión es O(log n), lo que da O(n log n) en el caso promedio. La trampa: una elección de pivote fija (siempre el último elemento, por ejemplo) alcanza su peor caso O(n²) exactamente con entradas ya ordenadas o en orden inverso — precisamente los dos órdenes que los benchmarks de este repositorio ya prueban para todos los demás algoritmos de ordenamiento. Esta implementación elige el pivote de forma uniformemente aleatoria dentro del rango actual antes de cada partición. Eso no elimina el peor caso — sigue siendo matemáticamente posible — pero ata el peor caso a la semilla aleatoria en lugar del orden propio de la entrada, que es lo que hace que quicksort sea seguro de ejecutar sobre una entrada que no controlas, en lugar de una mina terrestre esperando la única forma de entrada que lo rompe.

flowchart LR
    subgraph "partition around a pivot (7)"
        direction LR
        A0["5"] --- A1["3"] --- A2["9"] --- A3["1"] --- A4["7*"] --- A5["8"]
    end
    subgraph "after: smaller left, larger right, pivot fixed"
        direction LR
        B0["5"] --- B1["3"] --- B2["1"] --- B3["7*"] --- B4["9"] --- B5["8"]
    end

Ejemplo clásico

classic/QuickSort es genérico sobre Comparator<? super T> — sin atajo de Arrays.sort/Collections.sort — usando particionamiento de Lomuto con un pivote aleatorizado intercambiado a la última posición antes de cada llamada de partición. El sort(array, comparator) público usa un java.util.Random sin semilla; una sobrecarga sort(array, comparator, random) package-private acepta un Random inyectado para que las pruebas puedan ser determinísticas. QuickSortTest cubre un array desordenado, ya ordenado, ordenado de forma inversa, duplicados, un array de un solo elemento y uno vacío, un comparador personalizado (descendente), la sobrecarga pública sin semilla, y ambas protecciones contra argumento nulo.

Ejemplo aplicado: ordenamiento por percentil de reserva de siniestros de seguros

applied/ClaimAmountSort ordena un gran lote de siniestros de seguros por monto para el cálculo de reserva basado en percentil (por ejemplo, "qué monto de siniestro marca el percentil 95 este trimestre"). Las exportaciones de siniestros suelen llegar ya casi ordenadas — por ID de siniestro, que tiende a correlacionarse con la fecha de presentación, que a su vez se correlaciona débilmente con el monto para muchos tipos de siniestro — que es exactamente el tipo de entrada casi ordenada que haría que un quicksort no aleatorizado degradara hacia su peor caso. Aleatorizar el pivote es lo que mantiene esto seguro para ejecutarse sobre un lote real, no aleatorio de forma sintética. ClaimAmountSortTest cubre siniestros ordenados en orden ascendente de monto, que el array de entrada queda intacto, y la protección contra argumento nulo.

Benchmark

./gradlew :sorting:quick-sort:jmh

Ejecución real en esta máquina (JMH 1.37, JDK 26.0.2, 2 iteraciones de calentamiento + 3 iteraciones de medición, 1 fork). Ya ordenado y ordenado de forma inversa — los dos órdenes que serían catastróficos para un quicksort de pivote fijo — frente a una entrada totalmente aleatoria:

Ese es todo el punto, hecho medible: en size=10,000, lo aleatorio es solo ~2.2x más costoso que lo ya ordenado — no el 100x o más que mostraría el peor caso O(n²) de un quicksort no aleatorizado exactamente con esta entrada. El pivote aleatorizado está haciendo su trabajo. El crecimiento entre tamaños también confirma O(n log n), no O(n²): lo aleatorio pasa de size=1,000 a size=10,000 (10x los datos) a ~15.3x el costo — cerca del ~13.3x que predice una forma O(n log n), lejos del ~100x que mostraría un ordenamiento cuadrático para el mismo salto. Vale la pena compararlo con el benchmark de Merge Sort de este repositorio en la misma máquina: ambos caen en un rango similar en size=10,000 (quicksort ~1,000–2,200 µs aquí vs. merge sort ~950–1,700 µs) — un rendimiento de caso promedio genuinamente comparable, con quicksort sin pagar asignación de buffer auxiliar y merge sort sin correr riesgo de peor caso.

Cuándo no usarlo

• ¿Necesitas una cota garantizada de peor caso, no solo abrumadoramente probable — un sistema de tiempo real estricto, o una entrada que debas asumir como adversaria? El Merge Sort de este repositorio renuncia a la propiedad in-place a cambio de una cota que no depende de la suerte aleatoria.
• ¿Necesitas estabilidad (que los elementos iguales mantengan su orden original)? Este esquema de particionamiento no la preserva — el Merge Sort sí.
• ¿n muy pequeño? El factor constante menor de Insertion Sort gana antes de que el overhead de recursión se pague solo — que es exactamente la razón por la que las implementaciones de quicksort en producción recurren a insertion sort por debajo de un umbral de tamaño pequeño, el mismo hecho en el que se apoya el propio módulo de Insertion Sort de este repositorio.

Cobertura de pruebas

100% de cobertura de instrucciones, 100% de cobertura de ramas (JaCoCo). Reprodúcelo tú mismo:

./gradlew :sorting:quick-sort:jacocoTestReport

Informe en sorting/quick-sort/build/reports/jacoco/test/html/index.html.

Lectura complementaria

• Cormen, Leiserson, Rivest & Stein — Introduction to Algorithms (CLRS), 3.ª/4.ª ed., Capítulo 7, "Quicksort", incluyendo la sección 7.3, "A randomized version of quicksort" — el tratamiento formal exactamente de la estrategia de aleatorización que este módulo implementa.
• Sedgewick & Wayne — Algorithms, 4.ª ed., Capítulo 2.3, "Quicksort" — incluye los refinamientos prácticos de ingeniería (barajado aleatorio antes de ordenar, corte a insertion sort para subarrays pequeños) que las implementaciones de producción añaden sobre el algoritmo central.

Pruebas unitarias

package com.algorithms.sorting.quicksort.classic;

import org.junit.jupiter.api.Test;

import java.util.Comparator;
import java.util.Random;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class QuickSortTest {

    private static final Random SEEDED = new Random(42);

    @Test
    void sortsAnUnorderedArrayIntoAscendingOrder() {
        Integer[] array = {5, 3, 8, 1, 9, 2};

        QuickSort.sort(array, Comparator.naturalOrder(), SEEDED);

        assertThat(array).containsExactly(1, 2, 3, 5, 8, 9);
    }

    @Test
    void alreadySortedArrayStaysSorted() {
        Integer[] array = {1, 2, 3, 4, 5};

        QuickSort.sort(array, Comparator.naturalOrder(), SEEDED);

        assertThat(array).containsExactly(1, 2, 3, 4, 5);
    }

    @Test
    void reverseSortedArrayEndsUpAscending() {
        Integer[] array = {5, 4, 3, 2, 1};

        QuickSort.sort(array, Comparator.naturalOrder(), SEEDED);

        assertThat(array).containsExactly(1, 2, 3, 4, 5);
    }

    @Test
    void duplicatesAreHandledCorrectly() {
        Integer[] array = {3, 1, 3, 2, 1};

        QuickSort.sort(array, Comparator.naturalOrder(), SEEDED);

        assertThat(array).containsExactly(1, 1, 2, 3, 3);
    }

    @Test
    void singleElementArrayStaysUnchanged() {
        Integer[] array = {42};

        QuickSort.sort(array, Comparator.naturalOrder(), SEEDED);

        assertThat(array).containsExactly(42);
    }

    @Test
    void emptyArrayStaysEmpty() {
        Integer[] array = {};

        QuickSort.sort(array, Comparator.naturalOrder(), SEEDED);

        assertThat(array).isEmpty();
    }

    @Test
    void sortsUsingACustomComparatorForDescendingOrder() {
        Integer[] array = {1, 5, 3, 2, 4};

        QuickSort.sort(array, Comparator.reverseOrder(), SEEDED);

        assertThat(array).containsExactly(5, 4, 3, 2, 1);
    }

    @Test
    void publicSortMethodWorksWithoutAnExplicitRandom() {
        Integer[] array = {4, 2, 7, 1};

        QuickSort.sort(array, Comparator.naturalOrder());

        assertThat(array).containsExactly(1, 2, 4, 7);
    }

    @Test
    void rejectsANullArray() {
        assertThatThrownBy(() -> QuickSort.sort(null, Comparator.naturalOrder()))
                .isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void rejectsANullComparator() {
        assertThatThrownBy(() -> QuickSort.sort(new Integer[] {1, 2}, null))
                .isInstanceOf(IllegalArgumentException.class);
    }
}

package com.algorithms.sorting.quicksort.applied;

import org.junit.jupiter.api.Test;

import java.math.BigDecimal;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class ClaimAmountSortTest {

    @Test
    void sortByAmountOrdersClaimsAscending() {
        ClaimAmountSort sorter = new ClaimAmountSort();
        InsuranceClaim[] claims = {
                claim("mid", "500.00"),
                claim("high", "9000.00"),
                claim("low", "12.50"),
        };

        InsuranceClaim[] sorted = sorter.sortByAmount(claims);

        assertThat(sorted).extracting(InsuranceClaim::claimId).containsExactly("low", "mid", "high");
    }

    @Test
    void doesNotMutateTheInputArray() {
        ClaimAmountSort sorter = new ClaimAmountSort();
        InsuranceClaim[] claims = {claim("b", "200.00"), claim("a", "10.00")};

        sorter.sortByAmount(claims);

        assertThat(claims).extracting(InsuranceClaim::claimId).containsExactly("b", "a");
    }

    @Test
    void rejectsNullClaims() {
        ClaimAmountSort sorter = new ClaimAmountSort();

        assertThatThrownBy(() -> sorter.sortByAmount(null)).isInstanceOf(IllegalArgumentException.class);
    }

    private static InsuranceClaim claim(String id, String amount) {
        return new InsuranceClaim(id, new BigDecimal(amount));
    }
}

Ver informe completo de cobertura JaCoCo →