Ordenamiento por casilleros
# Ordenamiento por casilleros

El ordenamiento por casilleros (bucket sort o bin sort, en inglés) es un algoritmo de ordenamiento que distribuye todos los elementos a ordenar entre un número finito de casilleros. Cada casillero solo puede contener los elementos que cumplan unas determinadas condiciones. En el ejemplo esas condiciones son intervalos de números. Las condiciones deben ser excluyentes entre sí, para evitar que un elemento pueda ser clasificado en dos casilleros distintos. Después cada uno de esos casilleros se ordena individualmente con otro algoritmo de ordenación (que podría ser distinto según el casillero), o se aplica recursivamente este algoritmo para obtener casilleros con menos elementos. Se trata de una generalización del algoritmo Pigeonhole sort. Cuando los elementos a ordenar están uniformemente distribuidos la complejidad computacional de este algoritmo es de O(n).

El algoritmo contiene los siguientes pasos:

* Crear una colección de casilleros vacíos
* Colocar cada elemento a ordenar en un único casillero
* Ordenar individualmente cada casillero
* devolver los elementos de cada casillero concatenados por orden

## Pseudocódigo

Aquí elementos es la lista de datos a ordenar y n el número de casilleros que queremos usar. Para buscar el casillero adecuado para un elemento se puede utilizar la técnica que más convenga, según cómo queramos ordenar los datos. La función ordenar puede ser cualquier función de ordenamiento, incluso la propia bucket-sort.

## Algoritmo del cartero

El algoritmo del cartero (inglés: postman's sort) es una variante del bucket sort utilizada cuando los elementos a ordenar disponen de varias claves y/o subclaves. El nombre de este algoritmo viene del ejemplo de las oficinas postales; allí cuando hay que clasificar una carta para que llegue a su destino primero se clasifica según el país de destino, luego la ciudad o la región, después según la calle o el barrio de destino, etc. Es decir, este algoritmo utiliza varias claves para hacer ordenamientos sucesivos. La complejidad computacional es de O(cn), siendo c el número de claves que se utilizan para clasificar.

