En este artículo se describe el algoritmo de ordenamiento no comparativo pigeonhole y su implementación en Pyhton, C, y PHP.

Pigeonhole u ordenamiento por casilleros en un algoritmo de ordenamiento no comparativo que permite ordenar una lista de números enteros. Al ser un algoritmo no comparativo se logra el objetivo sin realizar operaciones de comparación entre los elementos de la lista.

El funcionamiento consiste en crear casilleros que correspondan a todos los valores enteros posibles entre el elemento menor y el mayor de la lista a ordenar. Cada uno de estos casilleros tendrá un contador que comenzará en 0 al iniciar el algoritmo.

La lista será recorrida y se irá sumando 1 al casillero correspondiente a cada elemento realizado. Finalmente se recorreran los casilleros vacíandolos y reconstruyendo la lista ordenada.

Este algoritmo de ordenamiento tiene varias limitaciones y desventajas:

• Solo puede utilizarse para valores enteros: Ya que se trabaja con la acumulación de apariciones de valores no puede utilizarse para ordenar números flotantes
• No es eficiente para rangos altos: Ya que se crea un casillero para cada entero posible entre el valor más pequeño y el más grande una lista con una rango de valores alto generará muchos casilleros, muchos de los cuales pueden estar siempre vaciós
• Solo se guarda el valor: A diferencia de otros algoritmos de entrenamiento solo se tiene en cuenta el valor por el cual se quiere ordenar y no el elemento completo por lo que no podría utilizarse para ordenar un objeto con múltiples atributos

Ordenamiento pigeonhole

Se comienza con una lista de elementos no ordenada. Se crean los casilleros que corresponderán a todos los números enteros que se encuentren entre el valor más bajo y el más alto de la lista. Cada casillero es un contador inicializado en 0.

Se recorre la lista y se suma uno al casillero correspondiente para cada elemento.

Una vez recorrido el arreglo se comienza con el proceso de vaciado de los casilleros. Para cada casillero se resta uno del contador y se asigna el valor correspondiente en el arreglo reemplazando el valor que contenga. El proceso se repite hasta que el casillero esté vacío y se pasa al siguiente. El proceso termina cuando todos los casilleros han sido vaciados.

Al finalizar el algoritmo la lista se encuentra ordenada.

Código

Python

def pigeonhole(arreglo):
	#Definir valor mínimo y máximo dentro del arreglo 
	minimo,maximo = min(arreglo),max(arreglo)
	#Definir tamaño de casilleros
	tam = maximo- minimo + 1
	#Crear casillero con todos los valores inicializados con 0
	casillas = [0] * tam 
	#Recorrer arreglo
	for valor in arreglo:
		#Sumar 1 en el casillero correspondiente al valor del arreglo		
		casillas[valor - minimo] += 1
	i = 0
	#Recorrer casilleros
	for j in range(tam):
		#Verificar que el casillero no está vacío
		while casillas[j] > 0:
			#Sacar un elemento del casillero
			casillas[j] -= 1
			#Cargar valor en el arreglo
			arreglo[i] = j + minimo
			i += 1              
 
arreglo = [5,7,4,7,8]
pigeonhole(arreglo)
print(arreglo)

PHP

<?php

function pigeonhole($arreglo)
{
	#Definir valor mínimo y máximo dentro del arreglo 
	$minimo = min($arreglo);
	$maximo = max($arreglo);
	#Definir tamaño de casilleros
	$tam = $maximo- $minimo + 1;
	#Crear casillero con todos los valores inicializados con 0
	$casillas = array_fill($minimo, $maximo, 0);
	#Recorrer arreglo
	foreach ($arreglo as $valor)
	{
		#Sumar 1 en el casillero correspondiente al valor del arreglo		
		$casillas[$valor] += 1;
	}
	
	$i = 0;
	#Recorrer casilleros
	foreach ($casillas as  $j=>$val)
	{
		#Verificar que el casillero no está vacío
		while ($casillas[$j] > 0)
		{
			#Sacar un elemento del casillero
			$casillas[$j] -= 1;
			#Cargar valor en el arreglo
			$arreglo[$i] = $j;
			$i += 1;
		}   
	}
	return $arreglo;
}

function mostrarLista($lista)
{
	for($i=0;$i<count($lista);$i++)
	{
		echo "$lista[$i] ";
	}
	echo "<br/>";
}         

//Función para mostrar lista
$arreglo = [5,7,4,7,8];
mostrarLista($arreglo);
$arreglo = pigeonhole($arreglo);
mostrarLista($arreglo);

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Tamanio del arreglo a ordenar

int* pigeonhole(int *, int);
int min(int *, int);
int max(int *, int);
void mostrarLista(int *, int);

int main(int argc, const char *argv[]){

	int i=0, j=0;
	int arreglo[]={5,7,4,7,8};
	//calcula la longitud del arreglo
	int len = sizeof(arreglo)/sizeof(*arreglo);

	//llama a la funcion de ordenamiento
	pigeonhole(arreglo, len);

	//muestra el arreglo ordenado
	mostrarLista(arreglo, len);

	return 0;
}

// Funcion para obtener el valor minimo
int min(int *arr, int len){
	int i=0;
	int minimo = *arr;
	for (i = 0; i < len; i++) {
		if(*(arr+i) < minimo)
			minimo = *(arr+i);
	}
	return minimo;
}

//Funcion para obtener el valor maximo
int max(int *arr, int len){
	int i=0;
	int maximo = *arr;
	for (i = 0; i < len; i++) {
		if(*(arr+i) > maximo)
			maximo = *(arr+i);
	}
	return maximo;
}

//Función para mostrar lista
void mostrarLista(int *arr, int len){
	int i=0;
	for (i = 0; i < len; i++) {
		printf("%d ", *(arr+i));
	}
	printf("\n");
}

//Funcion de Ordenamiento
int* pigeonhole(int *arreglo, int len){
	int i,j;

	//Definir valor mínimo y máximo dentro del arreglo
	int minimo = min(arreglo, len);
	int maximo = max(arreglo, len);
	int tamanio = maximo - minimo +1;

	//Crear casillero con todos los valores inicializados con 0
	int *casillas = (int*)malloc(tamanio * sizeof(int));
	memset(casillas, 0, tamanio*sizeof(int));

	i=j=0;
	//Sumar 1 en el casillero correspondiente al valor del arreglo
	for (i = 0; i < len; i++) {
		casillas[*(arreglo+i) - minimo]++; 
	}

	i=0;
	//Recorrer casilleros
	for (j = 0; j < tamanio; j++) {
		//Verificar que el casillero no está vacío
		while(*(casillas+j)>0){
			//Sacar un elemento del casillero
			casillas[j]--;
			//Cargar valor en el arreglo
			*(arreglo+i) = j+minimo;
			i++;
		}
	}
}

Este algoritmo no se encuentra entre los más eficientes ni rápidos pero es un buen ejercicio de programación y es interesante para realizar una introducción a métodos de ordenamiento no comparativo. Hasta la próxima!