bucketsort en arreglos y listas dobles: 2019

Que es bucket sort y como se utiliza en arreglos y listas dobles

el bucket sort (ordenamiento por casilleros o por cubos) es un algoritmo de ordenamiento que distribuye todos sus elementos que va a ordenar sea entre un numero finito de casilleros es decir la cantidad de datos que tiene . el bucket sort tiene los siguiente pasos.

ventajas:

Este algoritmo es eficiente cuando la cantidad de casilleros es menor a la cantidad de claves.
Si son enteros permite ordenar valores directos en un rango determinado por los valores que halla.
Es estable cuando existen claves iguales se preserva.

desventajas:

No es eficiente cuando la cantidad de casilleros es mayor a la cantidad de claves , tampoco cuando el rango es desconocido.
Este algoritmo necesita una gran cantidad de memoria extra , en ocasiones se requiere memoria extra
El algoritmo no funciona de manera correcta cuando las claves son muy largas como el tiempo de clasificación total es proporcional a la longitud de la clave y el numero de elementos a ordenar.

bucketsort aplicado en arreglos

que es un arreglo?

una arreglo(arrays) es una estructura de datos que nos permite almacenar un conjunto de datos de un mismo tipo.el tamaño de los arrays se declara en un primer momento y no puede cambiar.

código en arreglos en java

    public void bucketSort(){
       int mayor = 0 ;
        for (int i = 0; i < cont; i++) {
            
            if(array [ i ] > mayor){
               mayor = array[i]; 
            }
        }
     int cont =0;
     while(mayor>9){
         mayor=(mayor/10);
         cont++;
          }
    
    int factor =(int) Math.pow(10, cont);
    int pot = 0;
    int pos;
    int[] b = new int[array.length];
    for(int i=0; i < cont ;i++){
        pos=(array[i]* array.length)/factor;      
        while(b[pos]!=0){// hay colision
            //la soluciòn de la colisiòn
            //Somete a pos a otra formula que ubique el valor en otra posiciòn
            if((int)Math.pow(10, pot) < array.length-1){
                pos = array[i]% (int)Math.pow(10, pot);
                pot++;
                    } else {
                        pos++;
                    }
                }
                b[pos] = array[i];

            }
            array = b;
            for (int i = 0; i < cont; i++) {
                System.out.print(array[i] + ", ");
            }
        }
    }
}

bucketsort aplicado en listas dobles

que son las listas dobles

una lista dobles es una estructura de datos que consiste en un conjunto de nodos enlazados secuencial, cada nodo contiene dos campos,llamados enlaces, que son referencias al nodo siguiente y al anterior en la secuencia de nodos.

código en listas dobles en java

//bucketsort

public void bucketsort() {
nodo[] hash = new nodo[10];//equivale tabla hash
for (int i = 0; i < 10; i++) {//cantidad de casillas que tiene hash
hash[i] = new nodo();//metodo constructor vacio

}
int pos;//posicion que se va hacer en la tabla
nodo p , q;//punteros que e va a utilizar
while (cab != null) {
p = this.cab;//esta es la cabeza, puntero que se asigna la cabeza
cab = cab.getSig();//la cabeza se desplaza a la siguiente pos de p.
if (cab != null) {
cab.setSig(null);//rompe el enlaze de su posicion anterior

}
p.setSig(null);//rompe el enlaze con su posicion siguiente una lista y un nodo
pos = p.getId() % 10;// identificador lo divide modulativamente y un residuo de o , 9
if (hash[pos].getSig() != null) {
q = hash[pos].getSig();mueve la Q para recorrer al final de la lista
while (q.getSig() != null) {
q = q.getSig();//se desplaza el puntero

}
q.setSig(p);//rompe el enlaze en la tabla hash
p.setAnt(q);//lo une con el nodo anterior
} else {
hash[pos].setSig(p);//crea un enlaze en la posicion siguiente
p.setAnt(hash[pos]);//crea un enlaze con la posicion anterior
}
}//para ordenar los valores por su residuo
for (int i = 0; i < 10; i++) {//pasa por todas las posiciones de la tabla hash
if (hash[i].getSig() != null) {//hay nodos , si es igual a null no hace nada
if (this.cab != null) {//ya levanto datos
while (p.getSig() != null) {
p = p.getSig();//se mueve hasta el final de la lista
}
p.setSig(hash[i].getSig());
p.getSig().setAnt(p);//apunta o hace un anclaje
hash[i].setSig(null);//rompe con la tabla hash

} else {
this.cab = hash[i].getSig();//se asigna la cabeza del primer nodo
this.cab.setAnt(null);//conecta el nodo que hay que eliminar
hash[i].setSig(null);//rompe el puntero de la lista anterior
p = this.cab;