Cubeta – Bucket

Bucket Sort o Bin Sort es un algoritmo derivado del de Casillero o Pigeonhole que trabaja distribuyendo los elementos del vector en “Cangilones/Cubetas”, siendo el índice del vector de la cubeta el valor del elemento. Cada cubeta se clasifica individualmente por el propio algoritmo o por otro en función de los criterios de tamaño y tipo de ordenación.

 

 

 

Bucket es de los algoritmos más rápidos, junto con el de Casillero y puede ser adaptado al tratamiento de ordenaciones externas. Tiene el inconveniente de usar más memoria que otros y de ralentizarse cuando el rango de los valores de los elementos es grande o cuando todos los elementos caen en la misma cubeta. Es muy similar al Countig-sort (sus cubetas tienen un solo valor) y al planteamiento de Radix (las cubetas tienen valores basados ​​en los dígitos de sus valores), Todos ellos tienen la vitola de poder trabajar en tiempo lineal.

 

 

Rendimiento – Complejidad
Mejor caso Ω	Peor caso O	Media Θ	Espacio
(n)	(n2)	$k$ es el nº de cubetas. (n + k)	(n + k)

 

 

Implementación en lenguaje Java.

 public static int[] Ordenacangilon(int[] Vector) {
		int vm=valormaximo(Vector);
	    int [] cangilon=new int[vm+1];
	    for (int i=0; i<Vector.length; i++) {
	       cangilon[Vector[i]]++;
	    }
	    int salida=0;
	    for (int i=0; i<cangilon.length; i++) {
	       for (int j=0; j<cangilon[i]; j++) {
	    	   Vector[salida++]=i;
	       }
	    }
		return Vector;
	 }


	static int valormaximo(int[] Vector) 
	{
	    int valormaximo = 0;
	    for (int i = 0; i < Vector.length; i++) if (Vector[i] > valormaximo)
	            valormaximo = Vector[i];
	    return valormaximo;
	}

Rendimiento.

Estadística individual realizada con el mismo equipo y condiciones del resumen de estadísticas de ordenación.