El ordenamiento del palomar es un algoritmo de ordenamiento adecuado para procesar listas donde el número n de elementos y la longitud N del rango de posibles valores de clave son aproximadamente iguales. Requiere un tiempo O(n + N). Es similar al ordenamiento por cuentas, pero se diferencia en que "mueve los elementos dos veces: una vez para distribuirlos en cubetas y otra vez al destino final [mientras que] la ordenación por conteo construye un arreglo auxiliar y luego usa ese arreglo para calcular el destino final de cada elemento y moverlo allí".
Mecánica del algoritmo El algoritmo de ordenación por palomar funciona de la siguiente manera:
Dada una lista de valores a ordenar, se crea una disposición auxiliar de "nidos" inicialmente vacíos (análogo a un buzón de mensajes con forma de casillero en una oficina o escritorio), una paloma por cada clave en el rango de las claves de la lista original. Recorriendo la lista original, colocar cada valor en el compartimento correspondiente a su clave, de manera que cada compartimento contenga finalmente una lista de todos los valores con esa clave. Iterar sobre el conjunto lineal de compartimentos en orden ascendente de claves y, para cada compartimento, colocar sus elementos en la lista original en orden ascendente.
Pseudocódigo A continuación se muestra una implementación del algoritmo de ordenación por compartimentos en pseudocódigo. Esta función ordena la lista in situ y modifica la lista proporcionada:
function pigeonhole(array arr) is min ← min(arr) max ← max(arr) index ← 0 range ← max - min + 1 array tmp ← nueva matriz de longitud del rango
for i = 0 to range STEP 1 tmp[i] = 0
for i = 0 to length(arr) STEP 1 tmp[arr[i] - min] = tmp[arr[i] - min] + 1
for i = 0 to range STEP 1 while tmp[i] > 0 do tmp[i] = tmp[i] - 1 arr[index] = i + min index = index + 1
Ejemplo Supóngase que deben ordenarse estos pares de valores por su primer elemento:
(5, "hola") (3, "pastel") (8, "manzana") (5, "rey")
Para cada valor entre 3 y 8, se crea un casillero y luego se mueve cada elemento a su casillero:
3: (3, "pastel") 4: 5: (5, "hola"), (5, "rey") 6: 7: 8: (8, "manzana")
Luego, se itera sobre el array de casilleros en orden y los elementos se devuelven a la lista original.
La diferencia entre el ordenamiento por palomar y el ordenamiento por conteo radica en que, en este último, la matriz luneal auxiliar no contiene listas de elementos de entrada, sino solo conteos:
3: 1 4: 0 5: 2 6: 0 7: 0 8: 1
Para listas en las que N es mucho mayor que n, el ordenamiento por casilleros es una generalización más eficiente en espacio y tiempo.
Véase también Principio del palomar Ordenamiento Radix Ordenamiento por cuentas Cola de cubos, una estructura de datos de cola de prioridad relacionada
Referencias
Enlaces externos
Categoría:Algoritmos de ordenamiento