Clasificación por casilleros

El ordenamiento por casilleros es un algoritmo de ordenamiento adecuado para ordenar listas de elementos en las que el número n de elementos y la longitud N del rango de posibles valores clave son aproximadamente iguales. ^[1] Requiere un tiempo O ( n + N ). Es similar al ordenamiento por conteo , pero se diferencia en que "mueve los elementos dos veces: una vez a la matriz de contenedores y otra vez al destino final [mientras que] el ordenamiento por conteo crea una matriz auxiliar y luego usa la matriz para calcular el destino final de cada elemento y mover el elemento allí". ^[2]

El algoritmo del pigeonhole funciona de la siguiente manera:

1. Dada una matriz de valores para ordenar, configure una matriz auxiliar de "casilleros" inicialmente vacíos (análogos a un cuadro de mensaje de casillero en una oficina o escritorio), un casillero para cada clave en el rango de las claves en la matriz original.
2. Recorriendo la matriz original, coloque cada valor en el casillero correspondiente a su clave, de modo que cada casillero contenga eventualmente una lista de todos los valores con esa clave.
3. Iterar sobre la matriz de casilleros en orden creciente de claves y, para cada casillero, colocar sus elementos en la matriz original en orden creciente.

Ejemplo

Supongamos que uno estuviera ordenando estos pares de valores por su primer elemento:

• (5, "hola")
• (3, "pastel")
• (8, "manzana")
• (5, "rey")

Para cada valor entre 3 y 8 creamos un casillero y luego movemos cada elemento a su casillero:

• 3: (3, "pastel")
• 4:
• 5: (5, "hola"), (5, "rey")
• 6:
• 7:
• 8: (8, "manzana")

Luego, la matriz de casilleros se itera en orden y los elementos se mueven nuevamente a la lista original.

La diferencia entre la ordenación por casillero y la ordenación por conteo es que en la ordenación por conteo, la matriz auxiliar no contiene listas de elementos de entrada, solo recuentos:

• 3: 1
• 4:0
• 5: 2
• 6:0
• 7:0
• 8:1

Para matrices donde N es mucho mayor que n , la ordenación por cubos es una generalización que es más eficiente en el espacio y en el tiempo.

Véase también

• Principio del casillero
• Ordenamiento por base
• Cola de cubos , una estructura de datos de cola de prioridad relacionada

Referencias

1. "Diccionario de algoritmos y estructuras de datos del NIST: ordenación por casilleros".
2. Black, Paul E. "Diccionario de algoritmos y estructuras de datos". NIST . Consultado el 6 de noviembre de 2015 .