Matemáticamente el Principio del Casillero, “PigeonHole”, establece que: cuando varios objetos se colocan en casilleros y hay más objetos que casilleros, seguro que habrá uno o más casilleros que contengan al menos dos objetos. Tomando como ejemplo el de un palomar:
si hay n palomas y j huecos (n > j), existe al menos un hueco con al menos n/j palomas, es decir, el valor máximo es al menos, mayor que el valor medio.
La primera constatación de la aparición de este principio y su aplicación practica en las matemáticas fue en 1.834, en la publicación de Johann P. G. Lejeune Dirichlet, Schubfachprinzip (Principio del cajón). Dirichlet no fue el primero en hacer referencia a este principio, en 1.622 Jean Leurechon en el libro “SelectæPropositiones” lo propone como un elemento de enseñanza y Marin Mersenne lo traslada a sus escritos en 1.625.
Con independencia de cómo y dónde haya sido utilizado, lo que nos interesa del Principio del Casillero es la idea y cuál algoritmo lo utiliza, no hay que pensar mucho, lo utiliza el algoritmo del Casillero. Este algoritmo es adecuado para ordenar vectores donde el número de elementos y el número de valores posibles son aproximadamente los mismos, es de los más rápidos en todas las pruebas y no exige acciones de comparación. Requiere un tiempo medio de O ( n + Rango ) donde n es el número de elementos en el vector de entrada y ‘Rango’ es el número de valores posibles del vector.
| Rendimiento – Complejidad | |||
| Mejor caso Ω |
Peor caso O |
Media Θ |
Espacio |
| – | (n + 2R) | (n + 2R) | O(n + R) |
El algoritmo trabaja de la siguiente forma:
- Encuentra los valores máximos y mínimos del vector y de ellos obtiene el rango (máximo – mínimo + 1).
- Crea un vector del mismo tamaño que el rango. (Casilleros).
- Recorre los elementos del vector de entrada y coloca cada elemento, Vector [i], en su lugar dentro del Casillero. Inicia un bucle en el vector Casillero, en orden, y vuelve a colocar los elementos de los casilleros no vacíos en el vector original.
Ejemplo.
El algoritmo programado en Java.
Rendimiento.
Estadística individual realizada con el mismo equipo y condiciones del resumen de estadísticas de ordenación. He dividido la estadística en dos gráficos debido a la diferencia de duración del proceso respecto a los condicionantes de los vectores con clasificación parcial y con elementos de valor de 1 a 100 millones.
