Ordenamiento por conteo y radix en Java

Problema

Un millón de pedidos, cien zonas

La empresa de mensajería recibe un millón de pedidos para el día. Cada uno tiene una zona de entrega: un número de 0 a 99. Antes de que salgan las furgonetas, los pedidos se ordenan por zona, para que cada furgoneta pueda tomar su propia pila.

El ordenamiento por mezcla hace unos 18,7 millones de comparaciones con un millón de pedidos, y el de montículo no es mejor (mira el ordenamiento por montículo). Comparan pedido con pedido, porque no saben nada de la clave.

Pero aquí sabes mucho: hay solo cien zonas distintas. Lo mismo pasa con las valoraciones de un producto: de 1 a 5. Comparar un millón de pedidos para averiguar que 37 va antes que 38 es un trabajo que no hace falta hacer.

La idea

Cuenta en lugar de comparar

La clave es un entero pequeño. Así que puede ser un índice de un arreglo. El ordenamiento pasa a ser tres pasadas:

Contar. Un contador para cada zona. Cada pedido suma uno al contador de su zona.
Dónde empieza cada zona. La zona 0 empieza en el lugar 0. La zona 1 empieza tras todos los pedidos de la zona 0. Cada comienzo es el anterior más la cantidad de la zona anterior. Esto se llama suma de prefijos.
Colocar. Recorres los pedidos de izquierda a derecha. Cada uno va al comienzo de su zona, y el comienzo avanza uno.

Esto es el ordenamiento por conteo. Ni un solo pedido se compara con otro.

Ir de izquierda a derecha tiene una consecuencia importante: los pedidos de una zona se quedan en el orden en que llegaron. Si estaban ordenados por hora, dentro de su zona siguen por hora. Un ordenamiento así se llama estable. En la lección sobre estabilidad verás por qué importa tanto.

Míralo

Ocho pedidos, cuatro zonas

El número de zonas es un parámetro. Para el millón de pedidos es 100, aquí es 4, para que todo se vea:

record Order(int id, int zone) {}

static Order[] byZone(Order[] orders, int zones) {
    int[] count = new int[zones];
    for (Order o : orders) {
        count[o.zone()]++;
    }
    int[] start = new int[zones];
    for (int z = 1; z < zones; z++) {
        start[z] = start[z - 1] + count[z - 1];
    }
    Order[] out = new Order[orders.length];
    for (Order o : orders) {
        out[start[o.zone()]++] = o;
    }
    return out;
}

Order[] orders = {
    new Order(101, 2),
    new Order(102, 0),
    new Order(103, 3),
    new Order(104, 2),
    new Order(105, 1),
    new Order(106, 0),
    new Order(107, 2),
    new Order(108, 3)
};
for (Order o : byZone(orders, 4)) {
    System.out.println("zona " + o.zone() + ", pedido " + o.id());
}

zona 0, pedido 102
zona 0, pedido 106
zona 1, pedido 105
zona 2, pedido 101
zona 2, pedido 104
zona 2, pedido 107
zona 3, pedido 103
zona 3, pedido 108

static Order[] byZone(Order[] orders, int zones) {
    int[] count = new int[zones];
    for (Order o : orders) {
        count[o.zone()]++;
    }
    int[] start = new int[zones];
    for (int z = 1; z < zones; z++) {
        start[z] = start[z - 1] + count[z - 1];
    }
    Order[] out = new Order[orders.length];
    for (Order o : orders) {
        out[start[o.zone()]++] = o;
    }
    return out;
}

Paso a paso, en palabras

Ocho pedidos, cada uno con una zona de entrega de 0 a 3. Un contador por zona, todos en 0.
Contar: cada pedido suma uno al contador de su zona. Ningún pedido se compara con otro.
Dónde empieza cada zona: la zona 0 en el lugar 0, la zona 1 tras los dos pedidos de la zona 0, en el lugar 2; la zona 2 en 3, la zona 3 en 6. Cada comienzo es el anterior más la cantidad de la zona anterior.
Colocar, de izquierda a derecha: 101 va al comienzo de la zona 2, lugar 3, y el comienzo de la zona 2 avanza uno.
Ordenado por zona en 2n + k pasos. En la zona 2 los pedidos son 101, 104, 107: en el orden en que llegaron. Es un ordenamiento estable.

Los pedidos 101, 104 y 107 están en la zona 2. Llegaron en este orden y salieron en este orden.

start[...]++ coloca en el comienzo actual y luego lo avanza uno: ++ después de la expresión devuelve el valor antiguo.

Pruébalo

Completa

El comienzo de la zona z es el comienzo de la zona anterior más:

start[z] = start[z - 1] + ;

La idea

Cuánto cuesta: O(n + k)

Cada pedido se cuenta una vez y se coloca una vez: 2n pasos. Los comienzos son uno por zona: k pasos. En total O(n + k), donde k es el número de claves posibles. Memoria: el arreglo de contadores (k) y el arreglo con el resultado (n).

Aquí no hay comparaciones, así que Bench cuenta cada paso del ordenamiento por conteo: cada conteo, cada contador y cada colocación. El ordenamiento por mezcla cuenta sus comparaciones:

Ordenamiento por conteo (zonas 0–99) O(n)
Ordenar (merge sort) O(n log n)

Algoritmo	n = 10	n = 1000	n = 100.000	n = 1.000.000
Ordenamiento por conteo (zonas 0–99)	120	2100	200.100	2.000.100
Ordenar (merge sort)	21	8709	1.536.371	18.674.993

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.

Con un millón de pedidos el ordenamiento por conteo hace 2 000 100 pasos, y el de mezcla 18 674 993 comparaciones. La línea recta del conteo es O(n): el doble de pedidos, el doble de trabajo.

Más precisamente, para curiosos

¿Puede un ordenamiento por comparaciones ser más rápido que n log n? No. Con n elementos hay n! órdenes posibles, y cada comparación tiene dos respuestas. Para distinguir n! casos hacen falta al menos log₂(n!) comparaciones, y eso son unas n log₂ n. El ordenamiento por conteo esquiva este límite porque no compara: usa la clave como dirección.

Míralo

Ordenamiento radix: dígito a dígito

¿Y si la clave es mayor? Los códigos postales búlgaros tienen cuatro dígitos, de 1000 a 9999: 9000 contadores cada día. Los números de pedido tienen seis dígitos: 900 000 contadores.

El ordenamiento radix ordena dígito a dígito con el mismo conteo, pero con solo 10 contadores. Primero por el último dígito, luego por el anterior, y así hasta el primero (LSD, del dígito menos significativo). Cada pasada es un ordenamiento por conteo por un dígito:

static int[] byDigit(int[] codes, int exp) {
    int[] count = new int[10];
    for (int c : codes) {
        count[c / exp % 10]++;
    }
    int[] start = new int[10];
    for (int d = 1; d < 10; d++) {
        start[d] = start[d - 1] + count[d - 1];
    }
    int[] out = new int[codes.length];
    for (int c : codes) {
        out[start[c / exp % 10]++] = c;
    }
    return out;
}

int[] codes = {4003, 1504, 9000, 1000, 8001, 4000, 1404};
for (int exp = 1; exp <= 1000; exp *= 10) {
    codes = byDigit(codes, exp);
    System.out.println(Arrays.toString(codes));
}

[9000, 1000, 4000, 8001, 4003, 1504, 1404]
[9000, 1000, 4000, 8001, 4003, 1504, 1404]
[9000, 1000, 4000, 8001, 4003, 1404, 1504]
[1000, 1404, 1504, 4000, 4003, 8001, 9000]

Tras la primera pasada los códigos están ordenados por el último dígito. Tras la segunda, por los dos últimos. Tras la cuarta, por los cuatro.

Esto funciona solo porque cada pasada es estable. La pasada por centenas no desordena los códigos con las mismas centenas, y ya están ordenados por los dos últimos dígitos. 1000, 1404 y 1504 tienen el mismo primer dígito: la última pasada los deja en el orden que recibieron de las anteriores.

c / exp % 10 es el dígito: 4003 / 1000 es 4 con la división de enteros, y % 10 toma el último dígito.

Coste: d pasadas de n + 10 pasos, donde d es el número de dígitos. Para números de seis dígitos son 6 · (2n + 10):

Ordenamiento radix (6 dígitos) O(n)
Ordenamiento por conteo (zonas 0–99) O(n)
Ordenar (merge sort) O(n log n)

Algoritmo	n = 10	n = 1000	n = 100.000	n = 1.000.000
Ordenamiento radix (6 dígitos)	180	12.060	1.200.060	12.000.060
Ordenamiento por conteo (zonas 0–99)	120	2100	200.100	2.000.100
Ordenar (merge sort)	21	8709	1.536.371	18.674.993

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.

Pruébalo

Predice la salida

Una pasada por el último dígito (exp es 1). ¿Qué imprime el programa?

int[] codes = {31, 12, 22, 11};
System.out.println(Arrays.toString(byDigit(codes, 1)));

Respuesta

[11, 12, 22, 31]

[11, 31, 12, 22]

[31, 11, 12, 22]

Pruébalo

Encuentra el error

Alguien coloca los pedidos de atrás hacia delante. Las zonas salen ordenadas, pero dentro de la zona 2 algo no está bien:

static Order[] byZone(Order[] orders, int zones) {
    int[] count = new int[zones];
    for (Order o : orders) {
        count[o.zone()]++;
    }
    int[] start = new int[zones];
    for (int z = 1; z < zones; z++) {
        start[z] = start[z - 1] + count[z - 1];
    }
    Order[] out = new Order[orders.length];
    for (int i = orders.length - 1; i >= 0; i--) {
        out[start[orders[i].zone()]++] = orders[i];
    }
    return out;
}

Order[] orders = {
    new Order(101, 2),
    new Order(102, 0),
    new Order(103, 3),
    new Order(104, 2),
    new Order(105, 1),
    new Order(106, 0),
    new Order(107, 2),
    new Order(108, 3)
};
for (Order o : byZone(orders, 4)) {
    System.out.println("zona " + o.zone() + ", pedido " + o.id());
}

zona 0, pedido 106
zona 0, pedido 102
zona 1, pedido 105
zona 2, pedido 107
zona 2, pedido 104
zona 2, pedido 101
zona 3, pedido 108
zona 3, pedido 103

¿En qué línea está el error?

Elige la línea con el error.

La idea

Cuándo no funciona

k es enorme. Un precio en céntimos de euro de hasta 100 000 €: 10 millones de contadores para ordenar mil pedidos. El ordenamiento por mezcla termina con unas 10 000 comparaciones. El conteo compensa cuando k es aproximadamente n o menor.
La clave no es un entero. Nombres, direcciones, precios con decimales: no son índices de un arreglo. El radix puede ordenar strings carácter por carácter, pero solo si todos tienen la misma longitud o se rellenan.
Claves negativas. Funcionan si restas la menor: clave − min empieza en 0.

Por eso el sort incorporado de ninguno de los cuatro lenguajes es un ordenamiento por conteo. Tiene que ordenar cualquier cosa, y lo único que sabe de los elementos es cómo compararlos.

Más precisamente, para curiosos

Cómo es en los otros lenguajes: en Java Arrays.sort para un arreglo de int es quicksort de doble pivote, en C# Array.Sort es introsort, en Python sort y en JavaScript sort son variantes del ordenamiento por mezcla (TimSort). Todos comparan. El ordenamiento por conteo y el radix se escriben a mano cuando sabes que la clave es pequeña: zonas, valoraciones, años, códigos. Cómo ordenan los incorporados está en la lección sobre estabilidad.

Ejercicio

Reseñas por valoración

Resuelve la tarea en tu editor.

Valoraciones de 1 a 5. Doce reseñas de un producto tienen las valoraciones 5, 3, 4, 5, 1, 2, 5, 4, 4, 3, 5, 2. Cuenta con un arreglo de contadores cuántas hay de cada valoración, imprime las cantidades y después las valoraciones ordenadas, sin una sola comparación entre dos valoraciones.

1: 1
2: 2
3: 2
4: 3
5: 4
Ordenadas: [1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5]

Más tareas

Las reseñas, no solo las valoraciones. Cada reseña tiene un autor y una valoración. Ordena las reseñas por valoración con byZone y comprueba que las reseñas con la misma valoración se quedan en el orden en que se escribieron.
Números de seis dígitos. Ordena los números de pedido 482113, 105990, 482100, 300001, 105911 con radix. ¿Cuántas pasadas necesitas?
Temperaturas negativas. Ordena las temperaturas -3, 5, 0, -8, 12, 5 con el ordenamiento por conteo. ¿Qué restas de cada clave?

Test

Ponte a prueba

1. ¿Cuántos pasos hace el ordenamiento por conteo con n pedidos y zonas de 0 a k - 1?Unos 2n + k: contar, los comienzos de las zonas, colocarUnos n log nUnos n · k

2. ¿Cuándo es mala elección el ordenamiento por conteo?La clave es un precio en céntimos de euro de hasta 10 000 000, y hay 1000 pedidosLa clave es una zona de 0 a 99La clave es una valoración de 1 a 5

3. El ordenamiento radix ordena los códigos postales primero por el último dígito, luego por el anterior… ¿Qué debe conservar cada pasada?Solo el primer dígitoEl orden de los códigos con el mismo dígito: así no se pierde lo que ordenaron las pasadas anterioresNada, cada pasada empieza de nuevo

4. ¿Por qué el ordenamiento por conteo no es el ordenamiento incorporado de los lenguajes?Porque solo funciona con claves enteras pequeñas, mientras que el incorporado ordena cualquier cosa comparandoPorque es lentoPorque no es estable

Ordenamiento por conteo y radix

Cookies