Algoritmica Busqueda Y Ordenacion

Búsqueda y Ordenación
Algorítmica y complejidad

Sergio Benito Robles
Bh0003 GCT11

1. Descripción del método

El ordenamiento por casilleros (bucket sort en inglés) es un algoritmo deordenamiento que distribuye todos los elementos a ordenar entre un número finito de casilleros. Cada casillero sólo puede contener los elementos que cumplan unas determinadas condiciones. Lascondiciones 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 deordenación (que podría ser distinto según el casillero), o se aplica recursivamente este algoritmo para obtener casilleros con menos elementos.

El algoritmo contiene los siguientes pasos:
-Crearuna 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 ordenLos elementos se distribuyen en cubos.

Luego se ordenan los elementos de cada cubo.

2. Código fuente en java

public class BucketSort{public static void sort(int[] a, int maxVal){
int [] bucket=new int[maxVal+1];

for (int i=0;i<bucket.length; i++){
bucket[i]=0;
}

for (int i=0; i<a.length; i++){bucket[a[i]]++;
}

ArrayUtil.print(bucket);

int outPos=0;
for (int i=0;i<bucket.length; i++){
for (int j=0; j<bucket[i]; j++){
a[outPos++]=i;
}
}...