Casillero

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.

 

Marin MersenneJohann P. G. Lejeune Dirichlet

Rendimiento – Complejidad
Mejor caso Ω
Peor caso O
Media Θ
Espacio
(n + 2R) (n + 2R) O(n + R)

El algoritmo trabaja de la siguiente forma:

  1. Encuentra los valores máximos y mínimos del vector y de ellos obtiene el rango (máximo – mínimo + 1).
  2. Crea un vector del mismo tamaño que el rango. (Casilleros).
  3. 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.

 

Casillero. Algoritmo de ordenación 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.

 

 

Casillero Pigenhole. Estadística de Rendimiento de 10 a 100mil elementos

 

 

 

 

Casillero Pigenhole. Estadística de Rendimiento de 100mil a 1Millón