bucket sort ordenar un vector o array java usando un bucket o contenedor

[lucianoStaley]

hola amigos: una consulta tengo un dilema con el bucket sort necesito que me guien como hacer que el bucket ordene de mayor a menor (java) entiendo el concepto pero no hay caso que me resulte pls alguien que me pueda guiar se lo agradeceria un monton (soy estudiante informatica)

pd: muy buena pagina me han sacado de muchas dudas saludos a todos 

[Alex Rodríguez]

Hola, léete esto: https://www.aprenderaprogramar.com/foros/index.php?topic=1460.0

Indica cuál es el enunciado del problema (¿en qué consiste el bucket sort?) y pega el código que tengas desarrollado hasta el momento y en qué parte en concreto es en la que obtienes un error o tienes problemas, para de esa forma poder ayudarte.

Saludos.

[lucianoStaley]

hola mira el enunciado del problema es que debo orden un vector (arreglo) con numeros de tipo int ingresado previamente y ordenarlos de mayor a menor, bueno resulta que tengo solo la de ordenar de menor a mayor  con el bucket que es la comun  intente modificar pero no pude espero puedas guiarme un poco como hacer que haga el orden inverso? este es mi codigo es un metodo para el menor...

Código: [Seleccionar]

public static void sortMayorMenor(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]]++;
        }

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


[lucianoStaley]

bueno lo resolvi despues de tanto creo ques es por la falta de sueño que no dejaba ver con claridad... aqui les dejo el codigo por si alguien lo necesita busca en un vector de mayor a menor con un bucket sort  saludos a todos

Código: [Seleccionar]

public static void sortMayorMenor(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]]++;
        }

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

    }



[lucianoStaley]

corrijo: no busca solo ordena los numeros de un vector de  mayor a menor

[Alex Rodríguez]

Hola, veo que solo has incluido el método sortMayorMenor ¿puedes poner el código completo para así poder compilarlo? Saludos

[lucianoStaley]

por supuesto estimado

Código: [Seleccionar]

   
import java.util.*;

public class Vector_Sort {

    public static void sortMayorMenor(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]]++;
        }

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

    }

    public static void main(String[] args) {
   
        int[] vector = {4, 6, 12, 7, 20, 5};
                    maxVal = 100; //puede ser el valor que ustedes convenga
                    System.out.println("Antes: " + Arrays.toString(vector));
                    sortMayorMenor(vector, maxVal);
                    System.out.println("Despues:  " + Arrays.toString(vector));

                       
                 
           

    }
}
 

[Alex Rodríguez]

Gracias por compartir el código.

Para quien vea el código y quiera interpretar lo que hace, hace lo siguiente:

Crea un array denominado bucket de dimensiones aleatoriamente grandes (por ejemplo con 100 elementos). Toma un array a ordenar, por ejemplo array = {4, 6, 12, 7, 20, 5}

En el array bucket marca con un 1 las posiciones que se corresponden con valores en el array a ordenar. Por ejemplo bucket[4]=1, bucket[6]=1, bucket[12]=1, bucket[7]=1, bucket [20]=1, bucket[5] = 1

En este momento ya tenemos una ordenación sobre bucket, basada en los índices marcados, ya que lo anterior es lo mismo que bucket[4]=1, bucket[5] = 1, bucket[6]=1, bucket[7]=1, bucket[12]=1, bucket [20]=1

Finalmente partimos de la última posición válida de array y en un bucle vamos recorriendo todas las posiciones de bucket (desde 0 hasta 99 por ejemplo) y cuando encontramos un 1, asignamos a array el índice de bucket.

Por ejemplo:

indiceParaArray = 5

bucket[0]=0
bucket[1]=0
bucket[2]=0
bucket[3]=0
bucket[4]=1  -- > ahora array[5] = 4 y próximo indiceParaArray = 4
bucket[5]=1  -- > ahora array[4] = 5 y próximo indiceParaArray = 3
bucket[6]=1  -- > ahora array[3] = 6 y próximo indiceParaArray = 2
bucket[7]=1  -- > ahora array[2] = 7 y próximo indiceParaArray = 1
bucket[8]=0
bucket[9]=0
bucket[10]=0
bucket[11]=0
bucket[12]=1  --> ahora array[1]= 12 y próximo indiceParaArray = 0
bucket[13]=0
...
bucket[20]=1 -- > ahora array[0] = 20 y próximo indiceParaArray = -1
bucket[21]=0
...
así llegamos a bucket[99]=0 y el proceso termina

El array ha quedado ordenado: array = {4, 5, 6, 7, 12, 20}
   



En el código planteado, el doble bucle for no es necesario, ya que el for interno lo único que hace es dar pie a una ejecución del código interno si bucket [ i ] es igual a 1 (condición para entrar en el bucle), por tanto sería más claro escribirlo como:

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


Este método parece que tiene una complejidad buena en tiempo, O(n) con n = tamaño del bucket (que hemos de recorrer una vez para rellenarlo de ceros, y otra vez para encontrar los elementos marcados). Sin embargo, es ineficiente al usar un bucket de un tamaño aleatoriamente grande, y además no resultaría útil cuando entre los números a ordenar haya números aleatorios. Los números a ordenar tendrían que estar acotados dentro del tamaño del bucket.

En resumen, es un método curioso pero no puede considerarse un buen método de ordenación para casos generales.

Saludos,



CÓDIGO PRESCINDIENDO DEL DOBLE BUCLE

Código: [Seleccionar]

import java.util.*;
public class Vector_Sort {

    public static void sortMayorMenor(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]]++;
        }

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

    public static void main(String[] args) {

        int[] vector = {4, 6, 12, 7, 20, 5};
        int maxVal = 100; //puede ser el valor que ustedes convenga
        System.out.println("Antes: " + Arrays.toString(vector));
        sortMayorMenor(vector, maxVal);
        System.out.println("Despues:  " + Arrays.toString(vector));
    }
}


[Príncipe_Azul]

Hola, un gusto leerte mi amigo Alex, siempre tan bondadoso, te aprecio hermano.

Bueno quiero agregar un metodo que yo utilizo siempre que lo necesito, en java no se si existe la.funcion reverse(), me imaginobque si xD lo que yo hago para ordenar un array de mayor a menor, es usar la funcion sort() y luego usar la funcion reverse() wowwwww mas de uno se sorprende con este metodo, seguro que muchos saben este metodo,.pero muchos no, esto tambien lo utilizo cuando por ejemplo quiero ingresar datos en un Panel de un programa,.y los datos que se ingresan,.son leidos de un archivo de texto, pero el problema es que por ejemplo si en un archivo de texto hay 50 lineas y yo quiero volcar esa info en el panel,.en vez de salir en la primera fila del panel la primera linea del archivo, sale la ultima, osea que la ultima linea del archivo en vez de salir al final del panel,.sale arriba, osea en la prinera linea.

Ahi es cuando uso esa hermosa funciob reverse() luego de que lea el.contenido del archivo, entonces al volcar en el.panel,.ahi si sale perfectamente ordenadorl,.si java llegaria a tener reverse() que estoy muy seguro que si tiene,.entonces esa seria la solucion mas facil.y rapida de ordenar de mayor a menor los elementos de tipo int de un array.

Saludos cordiales.
Te mando un abrazo Alex a vos y a todos los demas compañeros.