Quicksort y el mal pivote en C#

Problema

La lista de precios ordenada se congela

La tienda ordena sus 100 000 productos con quicksort: con un catálogo mezclado son 2.136.015 comparaciones, y la página se abre al instante. Entonces el proveedor empieza a enviar su lista de precios ya ordenada por precio. El mismo botón «Ordenar por precio» piensa mucho tiempo y se detiene con un error:

static void QuickSort(int[] prices, int lo, int hi)
{
    RuntimeHelpers.EnsureSufficientExecutionStack();
    if (lo >= hi)
    {
        return;
    }
    int p = Partition(prices, lo, hi);
    QuickSort(prices, lo, p - 1);
    QuickSort(prices, p + 1, hi);
}

int[] prices = Catalog(100000);
Array.Sort(prices);
var worker = new Thread(() =>
{
    try
    {
        QuickSort(prices, 0, prices.Length - 1);
        Console.WriteLine("Ordenados");
    }
    catch (InsufficientExecutionStackException e)
    {
        Console.WriteLine("Pila agotada: " + e.GetType().Name);
    }
}, 1024 * 1024);
worker.Start();
worker.Join();

Pila agotada: InsufficientExecutionStackException

La entrada no es más grande, solo está ordenada. Una entrada ordenada debería ser la más fácil, y aquí es la más difícil. Para ver por qué, mira primero cómo funciona quicksort.

La idea

Pivote y partición

El ordenamiento por mezcla divide la lista en dos mitades sin mirar los precios, y todo el trabajo está en la mezcla. Quicksort hace lo contrario: el trabajo está en la división, y no hay mezcla. Sigue siendo divide y vencerás, como en el ordenamiento por mezcla.

Elige un precio como pivote. Aquí es el primer precio de la parte.
Reparte (partición): los precios menores que el pivote van a la izquierda, el resto a la derecha, y el pivote queda entre ellos. Ese es también su lugar definitivo.
Ordena la parte izquierda y la derecha con el mismo método. Una parte con un precio, o una vacía, ya está ordenada: es el caso base de la recursión.

La partición intercambia precios en el mismo arreglo, sin copias. Por eso quicksort no necesita O(n) de memoria extra como el ordenamiento por mezcla.

Míralo

La partición paso a paso

Aquí la partición es la de Lomuto: j recorre los precios uno a uno, e i marca el final de la zona izquierda, donde están los precios por debajo del pivote. Cada precio menor se une a la zona con un intercambio. Al final el pivote se intercambia con prices[i] y queda en su lugar:

static int Partition(int[] prices, int lo, int hi)
{
    int pivot = prices[lo];
    int i = lo;
    for (int j = lo + 1; j <= hi; j++)
    {
        if (prices[j] < pivot)
        {
            i++;
            (prices[i], prices[j]) = (prices[j], prices[i]);
        }
    }
    (prices[lo], prices[i]) = (prices[i], prices[lo]);
    return i;
}

Paso a paso, en palabras

El pivote es el primer precio, 45. i = 0 marca el final de la zona izquierda, la de los precios por debajo de 45. Todavía está vacía.
j = 1: 80 < 45? No. 80 se queda a la derecha, i no se mueve.
j = 2: 20 < 45? Sí. i pasa a ser 1 y 20 intercambia su lugar con 80: la zona izquierda crece.
j = 3: 65 < 45? No. 65 se queda a la derecha, i no se mueve.
j = 4: 10 < 45? Sí. i pasa a ser 2 y 10 intercambia su lugar con 80: la zona izquierda crece.
j = 5: 90 < 45? No. 90 se queda a la derecha, i no se mueve.
j = 6: 30 < 45? Sí. i pasa a ser 3 y 30 intercambia su lugar con 65: la zona izquierda crece.
j = 7: 55 < 45? No. 55 se queda a la derecha, i no se mueve.
j ha llegado al final: 7 comparaciones para 8 precios, n − 1. El pivote se intercambia con prices[i] = 30 y queda en el índice 3.
A la izquierda 30, 20, 10, todos por debajo de 45; a la derecha 80, 90, 65, 55. 45 está en su lugar definitivo, y las dos partes se ordenan por separado, en el mismo arreglo, sin memoria extra.

int[] prices = { 45, 80, 20, 65, 10, 90, 30, 55 };
int p = Partition(prices, 0, prices.Length - 1);
Console.WriteLine("[" + string.Join(", ", prices) + "], p = " + p);

[30, 20, 10, 45, 80, 90, 65, 55], p = 3

Partition devuelve dónde quedó el pivote, p = 3. Hay n − 1 comparaciones: cada precio excepto el pivote se compara con él exactamente una vez.

(prices[i], prices[j]) = (prices[j], prices[i]); es un intercambio con tuplas: el lado derecho se evalúa por completo antes de escribir el izquierdo.

Míralo

El quicksort completo

QuickSort reparte la parte de lo a hi y se llama a sí mismo para los dos lados del pivote. El propio pivote ya está en su lugar y no va a ninguno de los dos:

static void QuickSort(int[] prices, int lo, int hi)
{
    if (lo >= hi)
    {
        return;
    }
    int p = Partition(prices, lo, hi);
    QuickSort(prices, lo, p - 1);
    QuickSort(prices, p + 1, hi);
}

int[] prices = { 45, 80, 20, 65, 10, 90, 30, 55 };
Console.WriteLine("Antes: [" + string.Join(", ", prices) + "]");
QuickSort(prices, 0, prices.Length - 1);
Console.WriteLine("Después: [" + string.Join(", ", prices) + "]");

Antes: [45, 80, 20, 65, 10, 90, 30, 55]
Después: [10, 20, 30, 45, 55, 65, 80, 90]

La idea

n · log n en promedio, a veces n²

Lo que cuesta quicksort depende del pivote.

Un buen pivote está cerca de la mitad. Las dos partes son cada una más o menos la mitad, y como en el ordenamiento por mezcla hay unos log₂ n niveles. En cada nivel las particiones juntas pasan una vez por los n precios: en total, unas n · log₂ n. Con precios mezclados al azar, el primer precio es aleatorio, así que este es el caso promedio.
Un mal pivote es el precio menor (o el mayor) de la parte. La parte izquierda queda vacía, y la derecha solo pierde el pivote. Hay n niveles y (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 comparaciones. Eso es O(n²), tanto como los ordenamientos simples.

Con una entrada ordenada, el primer precio de cada parte es el menor. Así la entrada más fácil pasa a ser el peor caso:

static void QuickSort(int[] prices, int lo, int hi)
{
    if (lo >= hi)
    {
        return;
    }
    int p = Partition(prices, lo, hi);
    QuickSort(prices, lo, p - 1);
    QuickSort(prices, p + 1, hi);
}

static void QuickSort(int[] prices, int lo, int hi)
{
    if (lo >= hi)
    {
        return;
    }
    int k = Random.Shared.Next(lo, hi + 1);
    (prices[lo], prices[k]) = (prices[k], prices[lo]);
    int p = Partition(prices, lo, hi);
    QuickSort(prices, lo, p - 1);
    QuickSort(prices, p + 1, hi);
}

Paso a paso, en palabras

La lista de precios ya está ordenada, de 7 a 80. El pivote es el primer precio de cada parte.
El pivote 7 es el precio menor: 7 comparaciones y a la izquierda no va nada. La parte izquierda está vacía, la derecha tiene 7 precios.
Lo mismo en cada nivel: el pivote vuelve a ser el menor, y la parte pierde solo un precio. Cada nivel es una llamada anidada más.
8 niveles y 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 comparaciones, n(n − 1)/2. Con 100.000 precios: 4.999.950.000 comparaciones y 100.000 llamadas anidadas, más de las que cabe en la pila.
La solución: antes de repartir, un precio aleatorio de la parte pasa al principio. El resto del código es el mismo.
Una ejecución posible con la misma lista ordenada. Un pivote aleatorio suele estar en algún punto del medio, así que las dos partes reciben precios.
5 niveles en lugar de 8 y 17 comparaciones en lugar de 28. Otra ejecución sería algo distinta, pero el orden de la entrada ya no importa: en promedio, unas n · log₂ n.

Pruébalo

Predice la salida

Cinco precios, y el pivote es el primero, 50. ¿Qué imprime el programa?

static int Partition(int[] prices, int lo, int hi)
{
    int pivot = prices[lo];
    int i = lo;
    for (int j = lo + 1; j <= hi; j++)
    {
        if (prices[j] < pivot)
        {
            i++;
            (prices[i], prices[j]) = (prices[j], prices[i]);
        }
    }
    (prices[lo], prices[i]) = (prices[i], prices[lo]);
    return i;
}

int[] prices = { 50, 70, 20, 90, 40 };
int p = Partition(prices, 0, prices.Length - 1);
Console.WriteLine("[" + string.Join(", ", prices) + "], p = " + p);

Respuesta

[20, 40, 50, 70, 90], p = 2

[40, 20, 50, 90, 70], p = 2

[40, 20, 50, 90, 70], p = 0

Míralo

Mídelo: el primer pivote y un pivote aleatorio

Ejecuta quicksort con un catálogo mezclado y con uno ordenado. Se cuentan las comparaciones con el pivote. El primer pivote con 100 000 precios ordenados no se ejecuta de verdad: Bench lo estima a partir de la curva.

Quicksort, primer pivote, precios mezclados O(n log n)
Quicksort, primer pivote, precios ordenados O(n²)
Quicksort, pivote aleatorio, precios ordenados O(n log n)

Algoritmo	n = 10	n = 1000	n = 10.000	n = 100.000
Quicksort, primer pivote, precios mezclados	35	10.591	151.493	2.136.015
Quicksort, primer pivote, precios ordenados	45	499.500	49.995.000	≈ 4.999.500.000
Quicksort, pivote aleatorio, precios ordenados	21	10.576	153.725	2.316.280

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

static void QuickSort(int[] prices, int lo, int hi)
{
    if (lo >= hi)
    {
        return;
    }
    int k = Random.Shared.Next(lo, hi + 1);
    (prices[lo], prices[k]) = (prices[k], prices[lo]);
    int p = Partition(prices, lo, hi);
    QuickSort(prices, lo, p - 1);
    QuickSort(prices, p + 1, hi);
}

Con un catálogo mezclado de 1000 precios, el primer pivote hace 10.591 comparaciones. Con el mismo catálogo, ordenado, hace 499.500, exactamente 1000 · 999 / 2. Un pivote aleatorio con el catálogo ordenado: 10.576, casi tantas como con el mezclado. Con 100 000 precios el pivote aleatorio hace 2.316.280 comparaciones, y el primer pivote haría n(n − 1)/2 = 4.999.950.000 (Bench estima unos 5000 millones a partir de la curva).

Más precisamente, para curiosos

Los mismos números en tu lenguaje. El catálogo y las posiciones aleatorias salen de un pequeño generador con semilla, así que son los mismos en cada ejecución, en cada lenguaje y en Bench. Esta es la versión final de la lección (con recursión en la parte más pequeña, mira abajo), y además imprime lo profunda que llegó la pila:

static long comparisons = 0;
static long seed = 0;
static int deepest = 0;

static int[] Catalog(int n)
{
    int[] prices = new int[n];
    long x = 2026;
    for (int k = 0; k < n; k++)
    {
        x = x * 48271 % 2147483647;
        prices[k] = 1 + (int)(x % 10000);
    }
    return prices;
}

static void QuickSort(int[] prices, int lo, int hi, bool random, int depth)
{
    deepest = Math.Max(deepest, depth);
    while (lo < hi)
    {
        if (random)
        {
            seed = seed * 48271 % 2147483647;
            int k = lo + (int)(seed % (hi - lo + 1));
            (prices[lo], prices[k]) = (prices[k], prices[lo]);
        }
        int p = Partition(prices, lo, hi);
        if (p - lo < hi - p)
        {
            QuickSort(prices, lo, p - 1, random, depth + 1);
            lo = p + 1;
        }
        else
        {
            QuickSort(prices, p + 1, hi, random, depth + 1);
            hi = p - 1;
        }
    }
}

static int Partition(int[] prices, int lo, int hi)
{
    int pivot = prices[lo];
    int i = lo;
    for (int j = lo + 1; j <= hi; j++)
    {
        comparisons++;
        if (prices[j] < pivot)
        {
            i++;
            (prices[i], prices[j]) = (prices[j], prices[i]);
        }
    }
    (prices[lo], prices[i]) = (prices[i], prices[lo]);
    return i;
}

var runs = new (string Label, int N, bool Sorted, bool Random)[]
{
    ("primer pivote, mezclados", 1000, false, false),
    ("primer pivote, mezclados", 100000, false, false),
    ("primer pivote, ordenados", 1000, true, false),
    ("pivote aleatorio, ordenados", 1000, true, true),
    ("pivote aleatorio, ordenados", 100000, true, true),
};
foreach (var run in runs)
{
    int[] prices = Catalog(run.N);
    if (run.Sorted)
    {
        Array.Sort(prices);
    }
    comparisons = 0;
    seed = 12345;
    deepest = 0;
    QuickSort(prices, 0, prices.Length - 1, run.Random, 1);
    Console.WriteLine($"{run.Label}, n = {run.N}: {comparisons} comparaciones, profundidad {deepest}");
}

primer pivote, mezclados, n = 1000: 10591 comparaciones, profundidad 7
primer pivote, mezclados, n = 100000: 2136015 comparaciones, profundidad 11
primer pivote, ordenados, n = 1000: 499500 comparaciones, profundidad 2
pivote aleatorio, ordenados, n = 1000: 10576 comparaciones, profundidad 7
pivote aleatorio, ordenados, n = 100000: 2316280 comparaciones, profundidad 11

El ordenamiento por mezcla hace 1.536.292 comparaciones con los mismos 100 000 precios, menos que quicksort. Aun así, quicksort suele ser más rápido en la práctica: intercambia precios en el mismo arreglo, sin copias, y lee la memoria en orden.

La idea

Por qué se agota la pila

Cada llamada de QuickSort permanece en la pila de llamadas hasta que vuelve. Con un mal pivote la parte derecha es solo un precio más pequeña, así que las llamadas se anidan una dentro de otra: n niveles para n precios. La pila es limitada, a menudo alrededor de 1 MB, y con 100 000 llamadas anidadas se agota.

En C# un desbordamiento de pila real (StackOverflowException) no se puede capturar: el proceso simplemente se detiene. Por eso el ordenamiento aquí se ejecuta en un hilo con una pila de 1 MB, y RuntimeHelpers.EnsureSufficientExecutionStack() al principio de QuickSort lanza InsufficientExecutionStackException cuando la pila está casi llena. Esa excepción sí se puede capturar.

Aparte de la pila está el tiempo: n(n − 1)/2 comparaciones. Con 100 000 precios son unos 5000 millones, por eso el botón «piensa» antes de fallar.

La idea

Tres soluciones

Un pivote aleatorio. Antes de repartir, un precio aleatorio de la parte pasa al principio y se convierte en el pivote. Así ninguna entrada es mala a propósito: ordenada, invertida y mezclada dan todas unas n · log₂ n en promedio. El peor caso sigue existiendo, pero su probabilidad es despreciable: en cada nivel el precio aleatorio tendría que ser justo el menor o el mayor de la parte.

static void QuickSort(int[] prices, int lo, int hi)
{
    if (lo >= hi)
    {
        return;
    }
    int k = Random.Shared.Next(lo, hi + 1);
    (prices[lo], prices[k]) = (prices[k], prices[lo]);
    int p = Partition(prices, lo, hi);
    QuickSort(prices, lo, p - 1);
    QuickSort(prices, p + 1, hi);
}

Mediana de tres. En lugar de un precio aleatorio tomas el del medio por valor entre el primero, el de la mitad por posición y el último. Con una entrada ordenada es justo la mitad. Esta solución es el ejercicio del final de la lección.

Recursión en la parte más pequeña. La llamada es solo para la más pequeña de las dos partes, y la más grande queda para el bucle: lo o hi avanza y el bucle la reparte de nuevo. La parte más pequeña es como mucho la mitad, así que la pila tiene como máximo log₂ n niveles con cualquier pivote: hasta 17 con 100 000 precios (el programa con contadores llega a 11). Las comparaciones no bajan, así que esta solución va junto con el pivote aleatorio:

static void QuickSort(int[] prices, int lo, int hi)
{
    while (lo < hi)
    {
        int k = Random.Shared.Next(lo, hi + 1);
        (prices[lo], prices[k]) = (prices[k], prices[lo]);
        int p = Partition(prices, lo, hi);
        if (p - lo < hi - p)
        {
            QuickSort(prices, lo, p - 1);
            lo = p + 1;
        }
        else
        {
            QuickSort(prices, p + 1, hi);
            hi = p - 1;
        }
    }
}

int[] prices = Catalog(100000);
Array.Sort(prices);
QuickSort(prices, 0, prices.Length - 1);
Console.WriteLine("Ordenados: " + prices.SequenceEqual(prices.Order()));

Ordenados: True

Pruébalo

Encuentra el error

Los ocho precios salen casi ordenados:

int[] prices = { 45, 80, 20, 65, 10, 90, 30, 55 };
Console.WriteLine("Antes: [" + string.Join(", ", prices) + "]");
QuickSort(prices, 0, prices.Length - 1);
Console.WriteLine("Después: [" + string.Join(", ", prices) + "]");

Antes: [45, 80, 20, 65, 10, 90, 30, 55]
Después: [20, 30, 10, 45, 65, 80, 90, 55]

Este es el Partition del programa. ¿En qué línea está el error?

Elige la línea con el error.

Pruébalo

Rellena el hueco

La recursión va a la parte izquierda, la más pequeña. ¿Cuál es el nuevo valor de lo, para que el bucle siga con la parte derecha?

static void QuickSort(int[] prices, int lo, int hi)
{
    while (lo < hi)
    {
        int k = Random.Shared.Next(lo, hi + 1);
        (prices[lo], prices[k]) = (prices[k], prices[lo]);
        int p = Partition(prices, lo, hi);
        if (p - lo < hi - p)
        {
            QuickSort(prices, lo, p - 1);
            lo = ;
        }
        else
        {
            QuickSort(prices, p + 1, hi);
            hi = p - 1;
        }
    }
}

Ejercicio

Mediana de tres

Resuélvelo en tu editor.

Mediana de tres. Escribe Median(prices, lo, hi), que mira tres precios: el de lo, el de la mitad lo + (hi - lo) / 2 y el de hi, y devuelve la posición del que está en medio por valor. En QuickSort (la recursión simple de la lección), intercambia ese precio con prices[lo] antes de repartir. Cuenta las comparaciones con el pivote en Partition con el catálogo ordenado de la lección (catalog del programa con contadores, luego ordenado) con 1000 y con 100 000 precios.

mediana de tres, ordenados, n = 1000: 8005 comparaciones
mediana de tres, ordenados, n = 100000: 1773717 comparaciones

Compara con el primer pivote: 499.500 comparaciones con 1000 precios ordenados, y con 100 000 se agota la pila.

Más tareas

Una lista de precios invertida. Pasa el catálogo ordenado del más caro al más barato. ¿Cuántas comparaciones hace el primer pivote? ¿Y la mediana de tres?
Precios iguales. Pasa 1000 precios iguales. ¿Cuántas comparaciones hace la partición de Lomuto, y por qué? (Pista: nada es estrictamente menor que el pivote.)
El más caro primero. Cambia un carácter en Partition para que la lista salga del más caro al más barato.

Más precisamente

Quicksort dentro del ordenamiento incorporado

Quicksort lo inventó Tony Hoare en 1959, y sigue en el corazón del ordenamiento incorporado de muchos lenguajes, pero no en su forma pura: cada uno añade protecciones contra el mal pivote.

Más precisamente, para curiosos

Lomuto y Hoare. La partición de aquí es la de Lomuto: es fácil de leer, pero intercambia más. La partición de Hoare, la original, hace correr dos punteros desde los dos extremos el uno hacia el otro e intercambia solo pares de precios que están en el lado equivocado. Hace unas tres veces menos intercambios y se las arregla mejor con precios iguales, pero el pivote no necesariamente queda en su lugar definitivo, y el código es más fácil de escribir mal.

Precios iguales. Con muchos precios iguales, Lomuto aun así da partes malas: todo lo igual al pivote va a la derecha. Una partición en tres vías hace tres zonas: menores, iguales y mayores. Los iguales ya están y no entran en la recursión.

El ordenamiento incorporado. En C#, Array.Sort y List<T>.Sort son introsort: un quicksort con mediana de tres que cambia a ordenamiento por montículo cuando la recursión se hace demasiado profunda (unos 2 · log₂ n niveles), y a ordenamiento por inserción para partes pequeñas. Eso hace que el peor caso sea O(n log n). El std::sort de C++ hace lo mismo.

Quicksort no es estable: un intercambio puede saltar sobre un precio igual, y los productos iguales cambian su orden. Qué significa eso y cuándo importa está en la lección Ordenamiento estable y el ordenamiento incorporado.

Test

Ponte a prueba

1. ¿Qué hace repartir alrededor de un pivote?Divide el arreglo en dos partes exactamente igualesOrdena las dos mitades del arregloPone los precios menores a la izquierda del pivote y el resto a la derecha; el pivote queda en su lugar definitivo

2. El pivote es el primer precio. ¿Qué entrada es el peor caso?Una lista de precios mezclada al azarUna lista de precios que ya está ordenadaUna lista de precios con todos los precios distintos

3. ¿Por qué el quicksort simple falla con StackOverflowError (RecursionError, RangeError) con 100 000 precios ordenados?Cada nivel es una llamada anidada más, y hay 100 000 nivelesEl arreglo es demasiado grande para la memoriaLa recursión nunca llega al caso base

4. La recursión va solo a la parte más pequeña, y la más grande la maneja un bucle. ¿Qué se gana?La pila tiene como máximo log₂ n niveles de profundidad, sea cual sea el pivoteQuicksort pasa a ser estableLas comparaciones pasan a ser n log n incluso con una entrada ordenada

5. ¿Cuánta memoria extra necesita quicksort cuando recursa en la parte más pequeña?O(n²)O(n), tanto como el ordenamiento por mezclaO(log n): solo la pila

Quicksort y el mal pivote

Cookies