Algoritmo BucketSort en java

Hola querido publico
hoy hablaremos sobre un algoritmo BucketSort el cual sirve para dos cosas:

1. Para ordenar un conjunto de datos.
2. Para que los maestros puedan poner tareas.

Este algoritmo consiste en iterar sobre todo el conjunto de datos e ir añadiendo esto datos a una serie de listas finitas que contendrán datos con un rango de valores.

Cada una de estas listas tendrá un conjunto con datos que sera mas fácil ordenarlos
por lo que las comparaciones necesarias se reducen drasticamente.


Como veras este algoritmos sirve para simplificar el ordenamiento y se puede usarse solo o con cualquier otro algoritmo de ordenamiento.

El Lenguaje que utilizaremos hoy sera Java, pues es en el lenguaje en que están solicitando implementar el algoritmo y por que nos gusta java.

    1 import java.util.*;
    2 
    3 
    4 public class BucketSort
    5 {
    6 
    7     public static Vector<Integer> sort(Vector<Integer> lista, int inferior,int superior)
    8     {
    9         int rango= (superior-inferior);
   10         int bucket_size = rango/10;
   11 
   12         Vector<Vector> listas = new Vector<Vector>();
   13         /* creamos las listas de ordenamiento */
   14         for(int i=0;i<10;i++)
   15             listas.addElement(new Vector<Integer>());
   16 
   17         /*
   18            agregamos cada uno de los elemento en la lista que corresponde
   19          */
   20         for(int i=0;i<lista.size();i++)
   21         {
   22             /* calculamos en la lista que le corresponde */
   23             int casilla = (lista.elementAt(i)-inferior)/bucket_size;
   24             /* Agregamos el elemento a la lista calculada */
   25             Vector<Integer> vCasilla = listas.elementAt(casilla);
   26             vCasilla.addElement(lista.elementAt(i));
   27         }
   28 
   29         /* Ordenamos las listas con un metodo de ordenamiento
   30            en este caso utilizaremos el mismo metodo de ordenamiento
   31            el BucketSort recursivo.  */
   32         Vector<Integer> out= new Vector<Integer>();
   33         for(int i=0;i<listas.size();i++)
   34         {
   35             int inf= inferior+(i*bucket_size);
   36             int sup= inferior+(i*bucket_size)+bucket_size;
   37             /* en tmp vamos a guardar cada una de las listas pero ya ordenadas */
   38             Vector<Integer> tmp = null;
   39             /* si el rango es igual a 1 quiere decir que ya no hay por que ordenar si la lista tiene un elemento quiere decir que la lista esta ordenada */
   40             if( sup-inf == 1 || listas.elementAt(i).size() == 1)
   41             {
   42                 tmp =listas.elementAt(i);
   43             }
   44             else
   45             {
   46                 /*si no se cumple ninguna de las condiciones anteriores entonces la lista no esta ordenada pero procedemos a ordenarla */
   47                 tmp =  BucketSort.sort(listas.elementAt(i),inf,sup);
   48             }
   49             /*
   50                temp contiene los elementos de una lista ordenada
   51                Agregamos todos los elementos de las listas a una sola lista
   52              */
   53             for(int j=0;j<tmp.size();j++)
   54                 out.addElement(tmp.elementAt(j));
   55         }
   56         /*regresamos el contenido de todas las listas en una sola */
   57         return out;
   58     }
   59     public static void main(String [] args)
   60     {
   61         Random r = new Random();
   62         Vector<Integer> lista = new Vector<Integer>();
   63 
   64         for(int i=0;i<1000;lista.addElement(r.nextInt(1000)),i++);
   65         System.out.println("Imprimiendo generados");
   66         for(int i=0;i<lista.size();System.out.println(lista.elementAt(i++)));
   67 
   68         Vector<Integer> resultado = BucketSort.sort(lista,0,1000);
   69         System.out.println("Imprimiendo resultados");
   70         for(int= 0;i<resultado.size();i++)
   71             System.out.println(resultado.elementAt(i));
   72 
   73     }
   74 
   75 }