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) | 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.