Método de ordenamiento por Radix sort: Metodo de ordenacion por radix sort

MÉTODO DE ORDENAMIENTO POR RADIX SORT

Este método se basa en la clasificación de los datos que queremos ordenar por medio de una clave, esta clave debe ser una característica de cada dato que pueda ser descompuesta en elementos mas pequeños y que permita clasificar los elementos ordenándolos poco a poco.

En el primer paso en la parte de arriba, vemos una serie de números que están desordenados, que en la parte inferior se clasifican ordenadamente según el numero de veces que se repiten en la parte de arriba, colocándole un null en los números que no aparecen en la secuencia.

después de que han sido ordenados, miramos si algún numero se repite mas de una vez, en el caso de que se repita, se coloca "n" veces el numero en la misma posición.

ya al a ver acabado este proceso, procedemos a mirar si algún numero sigue desordenado, de lo contrario entonces ya damos por finalizado la ordenación de nuestros números.

Método implementado en java

A continuación daremos paso a la explicación de como seria este método implementado en java teniendo como referencia el siguiente código

1º

public class RadixSort{
public static void radixSort(int[] arr){
if(arr.length == 0)
return;
int[][] np = new int[arr.length][2];
int[] q = new int[0x100];
int i,j,k,l,f = 0;
for(k=0;k<4;k++){
for(i=0;i<(np.length-1);i++)
np[i][1] = i+1;
np[i][1] = -1;
for(i=0;i<q.length;i++)
q[i] = -1;
for(f=i=0;i<arr.length;i++){
j = ((0xFF<<(k<<3))&arr[i])>>(k<<3);
if(q[j] == -1)
l = q[j] = f;
else{
l = q[j];
while(np[l][1] != -1)
l = np[l][1];
np[l][1] = f;
l = np[l][1];
}
f = np[f][1];
np[l][0] = arr[i];
np[l][1] = -1;
}
for(l=q[i=j=0];i<0x100;i++)
for(l=q[i];l!=-1;l=np[l][1])
arr[j++] = np[l][0];
}
}
public static void main(String[] args){
int i;
int[] arr = new int[15];
System.out.print("original: ");
for(i=0;i<arr.length;i++){
arr[i] = (int)(Math.random() * 100);
System.out.print(arr[i] + " ");
}
radixSort(arr);
System.out.print("\nordenado: ");
for(i=0;i<arr.length;i++)
System.out.print(arr[i] + " ");
System.out.println("\finalizado");
}
}

como se puede observar no es un código demasiado complejo. Se compone de :

1-Primero declaramos las variables para saber que tipo de datos va a ser si positivo , negativo o otro, después creamos el arreglo que vamos a utilizar para desplazarnos por los números que vayan a ser elegidos, colocandole unos "for" para que haga una diferente acción dependiendo del ordenamiento, escribiendo los procesos necesarios en cada uno de ellos, como se mira a continuación.

2- ya al a ver terminado de colocar los "for" necesarios para recorrer nuestro arreglo, lo que sigue es ya lo mas sencillo, lo único que nos queda es colocar los textos que van a aparecer en pantalla y los números que vamos a ordenar. Para esto utilizamos un "arr[i] = (int)(Math.random() * 100);" y lo multiplicamos por el numero que queremos que llegue, en mi caso sera por 100 ya que no quiero que me muestre numero muy grandes, el resto lo que hace es

que nos suelta números al azar para que después mediante el anterior codigo lo recorra y lo ordene. Cuando ya tenemos los números que vamos a ordenar lo único que queda es colocar el texto que va a parecer para hacerlo mas sencillo de entender para el usuario, y listo ya tenemos nuestro codigo terminado.

referencias:

-Código sacado de :MODERADOR, Leyer. Algoritmo Radix Sort En Java. [EN LINEA]. 2009. [Citado en 16 de Octubre de 2017]. Disponible en internet: <http://foro.elhacker.net/java/algoritmo_radix_sort_en_java-t276529.0.html>

POR LISTAS DOBLES

Este método se realizo con interfaz grafico asi que procederemos a explicar su realización paso a paso.

¿En que consiste una lista doble y en que se diferencia de la normal?

1.* Consiste en una secuencia de nodos en los que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros al nodo anterior o posterior, y a diferencia del normal este permite inserciones y eliminación de nodos en cualquier punto de la lista.

Dicho esto ahora explicaremos el proceso a realizar para crear el programa.

1-creamos tres clases para lo que necesitaremos, en este caso las llamaremos de este modo : cNodo, nodo y Ordenacion.

* Nodo: aquí lo que haremos sera declarar las variables que vamos a utilizar y utilizando Getter and Setter añadiremos los public para cada una de las variables como podemos observar en la siguiente imagen.

2-cNodo: En este viene lo mas complicado, aqui empezaremos creando un "create" donde retornaremos los valores principales en este caso " id y valor" que estaban en el nodo. Seguiremos con el insert donde sea para si la lista tiene datos o esta vacia apoyandonos del null y unos "if" para hacer las condiciones necesarias.

Despues crearemos un Showall para leer los datos y recorrer las lista seguido de un select para contar los elementos de los que disponemos y para esto utilizamos un "while" ya que tenemos una condicion ya dicha que seria siempre que fuera diferente de null

seguimos con el search donde se encontrara una de las partes importantes, ya que dependiendo de done se encuentre se moverá a la derecha o a la izquierda para ordenarlo, para esto nos apoyaremos de unos "if" y "else" en caso de que no cumpla lo del "if".

A continuación pondremos un update que sera donde actualizamos la información con respecto a de que manera se van ordenando y el movimiento de izquierda o derecha que ocurre, y mediante se va organizando tenemos que colocar un delete para que valla borrando y reposicionando los nodos de acuerdo a como van estando. para terminar con este proceso y pasar a los de ordenación colocamos exchange que es donde recae el ordenarlo ya definitivamente.

Ahora si ya viene el método radix que en realidad es bastante corto

aqui declararemos el nodo con el numero diez ya que es el numero de elementos de la tabla hash, despues utilizamos un "for" para saber el numero de cada espacio y así lo coloque donde es.

3-por ultimo viene la interfaz donde ya se coloca dependiendo del gusto de cada uno y según los botones que le vayamos a colocar lo programaremos para que nuestro programa quede listo para ordenar los números que se le coloquen.

link de descarga del programa: http://www.mediafire.com/file/tcdyfat4dy9zctc/listas+dobles+con+radixSort.zip

1.referencia : WIKIPEDIA, Ordenamiento Radix Sort. [EN LINEA]. 2011. [Citado en 23 de Octubre de 2017]. Disponible en internet: <https://es.wikipedia.org/wiki/Ordenamiento_Radix>

Método de ordenamiento por Radix sort

lunes, 16 de octubre de 2017

Metodo de ordenacion por radix sort