1302
« en: 24 de Noviembre 2014, 10:17 »
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
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));
}
}
Mostrar Mensajes
RSS