Radix Sort
Radix Sort
Radix Sort
2011-II
Universidad Nacional Micaela Bastidas de Apurmac Escuela Acadmica Profesional de Ingeniera Informtica y Sistemas
INTEGRANTES
: Damian Elguera Yandali Sarmiento Ponce Hamely Utani Valdez Dalia del Milagro Zuiga Mendoza Ricardo Manuel MTODO DE ORDENAMIENTO RADIX SORT
DOCENTE
2011-II
INDICE
1.1 ANTECEDENTES E HISTORIA 1.2 DEFINICIN 1.3 ALGORITMO 1.4 EJEMPLOS OPTIMIZACIN 1.5 ANLISIS DEL ALGORITMO 1.6.1 ESTABILIDAD 1.6.2 TIEMPO 1.6 VENTAJAS
2011-II
MTODO DE ORDENAMIENTO: RADIX ANTECEDENTES: Es el algoritmo de las mquinas que ordenaban las tarjetas que se utilizaban para programar en el pasado. Estas tarjetas tenan una matriz de 80 columnas y 12 filas. La mquina se usaba para ordenar, contando con 12 casilleros siendo capaz de determinar, dada una columna, a que casillero deba ir a parar una tarjeta dependiendo de cul de los 12 casilleros tena el agujero. Luego de una pasada por la mquina, quedaban 12 pilas de tarjetas distribuidas en los 12 casilleros. Si esto lo aplicamos al ordenamiento de cualquier nmero natural de dgitos significativos, se pensara en 10 casilleros enumerados de 0-9 y que cada digito en particular se distribuira con la mquina.
DEFINICIN: Es un algoritmo que ordena y procesa sus dgitos de forma individual. Este mtodo se puede considerar como una generalizacin de la clasificacin de las urnas.
2011-II
En el siguiente ejemplo se explicar la secuencia y pasos que se lleva a cabo en el algoritmo. Ingresamos 8 nmeros cualesquiera, ordenamos de menor a mayor utilizando el mtodo radixsort.
32
224
16
15
31
169
123
252
1. Cada nmero se debe ordenar segn el valor de cada dgito, es decir en unidades, decenas y centenas.
C 0 2 0 0 0 1 1 2
D 3 2 1 1 3 6 2 5
U 2 4 6 5 1 9 3 2
2. Seguidamente se tiene 10 casilleros enumerados del 0 al 9 y que, dado un dgito en particular; se distribuir los nmeros en las diversas casillas, comenzando del valor menos significativo en este caso las unidades. 0k9 ={0,1,2,3,4,5,6,7,8,9} MTODO DE ORDENAMIENTO RADIX SORT
1 31
2 32 252
3 123
4 224
5 15
6 16
9 169
3. Luego pasar a las decenas para que nuevamente se reordenen los nmeros.
2011-II
8 9
1 15 16
2 123 224
3 31 32
5 252
6 169
2 224 252
15
16
31
32
123
169
224
252
6. En conclusin: La idea clave de la ordenacin Radixsort es clasificar por urnas primero respecto al dgito de menor peso (menos significativo) dk, despus concatenar las urnas, clasificar de nuevo respecto al siguiente dgito dk1, y as sucesivamente se sigue con el siguiente dgito hasta alcanzar el dgito ms significativo dl, y es cuando la secuencia estar ordenada. La concatenacin de las urnas consiste en enlazar el final de una con el frente de la siguiente. a. Estabilidad: Este algoritmo se considera estable si preserva el orden relativo de llaves iguales en la estructura de datos. b. Tiempo: el tiempo de total del Radix Sort es: es el nmero de valores diferentes del tipo . ( ). MTODO DE ORDENAMIENTO RADIX SORT
2011-II
c++ #include<conio.h> #include<stdio.h> #include<iostream.h> #include <math.h> #include<iomanip.h> #define MAX 100
int A[50] = {NULL}, i; static int n; int Veces; cout<<"====ORDENAMIENTO POR RADIX SORT=====\n"<<endl; cout<<"====ORDENAMIENTO POR RADIX SORT=====\n"<<endl; cout<<"INGRESE LA CANTIDAD DE NUMEROS A ORDENAR: "; cin>>Veces; cout<<"INGRESE LOS "<<Veces<<" NUMEROS: "<<endl; for ( n=0;n<Veces; n++ ) // indica que n es verdadero // se envia los parametros al metodo Radix MTODO DE ORDENAMIENTO RADIX SORT cin>>A[n]; if (n)
cout<<"LOS "<<Veces<<" NMEROS ORDENADOS SON: "<<endl; for (i = 0; i < n; i++) cout<<"A["<<i<<"]="<<A[i]<<endl; getch(); return 0; } void radixsort(int A[], int n)
2011-II
while (first != -1) { p = first; first = node[first].next; y = node[p].info; MTODO DE ORDENAMIENTO RADIX SORT exp = pow(10, k-1); j = (y/exp) % 10; q = rear[j]; if (q == -1) front[j] = p; else node[q].next = p; rear[j] = p; }
2011-II
2011-II
EJEMPLOS: 1. Ordenar la siguiente sucesin de nmeros en forma ascendente. 15, 20, 10, 89, 49, 23 y 13. Solucin:
Nmeros Originales:15 , 20 , 10 , 89 , 49 , 23 y 13
Colocando todos los nmeros con el orden que nos dieron, en la tabla de valor de Digito :
Decena 1 2 1 8 4 2 1
Unidad 5 0 0 9 9 3 3
Distribuyendo los nmeros empezando del valor menos significativo Primera Pasada (Unidades):15 , 20 , 10 , 89 , 49 , 23 y 13
0 1 2 3 4 5 6 7 8 9
20 , 10
23 , 13 15
89 , 49
Casillero [0,9]
Primera pasada
2011-II
20 , 10 , 23 , 13 , 15 , 89 , 49
Segunda Pasada (Decenas) :20 , 10 , 23 , 13 , 15 , 89 , 49 Casillero [0,9] Segunda pasada
0 1 2 3 4 5 6 7 8 9
10 , 13 , 15 20 , 23 49
89
10 , 13 , 15 , 20, 23,49,89
Los nmeros ordenados de forma ascendente son :
10 13 15 20 23 49 89
MTODO DE ORDENAMIENTO RADIX SORT
1 0
2011-II
Colocando todos los nmeros con el orden que nos dieron, en la tabla de valor de Digito: Unidad de Millar Centena Decena Unidad
0 0 0 0 0 0 2 0
0 2 7 0 2 0 8 0
1 6 8 0 1 4 5 0
6 3 9 4 2 8 4 1
Distribuyendo los nmeros empezando del valor menos significativo Primera Pasada (Unidades) :16 , 263 , 789 , 4 , 212 , 48 , 2854, 4 Casillero [0,9]1ra Pasada
16 48 789
0 1 2 3 4 5 6 7 8 9
1 1
2011-II
Segunda Pasada (Decenas):01 , 212 , 263 ,04 , 2854 , 16 , 48 , 789 Casillero [0,9] 2da Pasada
0 1 2 3 4 5 6 7 8 9
Resultado de acuerdo al Cuadro:
1,4 212, 16
Tercera pasada (Centenas): 001 , 004 , 212 , 016 , 048 , 2854 , 263 , 789 Casillero [0,9]3ra Pasada
789 2854
0 1 2 3 4 5 6 7 8 9
1,4,16,48 212,263
1 2
2011-II
Cuarta Pasada (Unidad de millar):0001 , 0004 , 0016 ,0048 ,0212 , 0263 , 0789 , 2854 Casillero [0,9] 4ta Pasada
0 1 2 3 4 5 6 7 8 9
1,4,16,48,212,263,789 2854
1 , 4 , 16 , 48 , 212 , 263 , 789 , 2854 Los nmeros ordenados de forma ascendente son :
16
1 3
2011-II
OPTIMIZACIN La optimizacin es el proceso de ajuste del rendimiento de un archivo ejecutable con el fin de obtener el mejor rendimiento y el menor tamao del cdigo. Objetivo: Mejorar el cdigo, preservando el significado del programa. Factores a optimizar: Velocidad de ejecucin Tamao del programa Necesidades de memoria El ordenamiento es razonablemente eficiente si el nmero de dgitos en las llaves no es demasiado grande. Si las mquinas tienen la ventaja de ordenar los dgitos (sobre todo si estn en binario) lo ejecutaran con mucho mayor rapidez de lo que ejecutan una comparacin de dos llaves completas. El Radixsort es potencialmente un algoritmo muy eficiente gracias a una complejidad lineal en el nmero de datos a ordenar. Desde un punto de vista del algoritmo secuencial, Radixsort muestra una pobre explotacin de la jerarqua de memoria cache del procesador. En el caso de los conjuntos de datos no caben en ningn nivel de la memoria cach del procesador. Una forma de optimizar desde el punto de vista del algoritmo paralelo, la solucin bsica puede tener un desequilibrio de carga en cada iteracin del algoritmo (ordenacin de cada digito). Estos se comparan con los anteriores algoritmos paralelos de ordenacin con los datos de memoria, demostrando que el algoritmo que se propone es el ms rpido para datos de clave y puntero de 32 y 64 bits sin embargo este algoritmo el mismo nmero de pasos de comunicacin que el algoritmo bsico de Radixsort paralelo, por lo que tampoco explotan la jerarqua de memoria del computador. MTODO DE ORDENAMIENTO RADIX SORT
1 4
2011-II
La eficiencia de este algoritmo depende en que las llaves estn compuestas de bits aleatorios en un orden aleatorio. Si esta condicin no se cumple ocurre una fuerte degradacin en el desempeo de estos mtodos. Adicionalmente, requiere de espacio adicional para realizar los intercambios. Los algoritmos de ordenamiento basados en radix se consideran como de propsito particular debido a que su factibilidad depende de propiedades especiales de las llaves, en contraste con algoritmos de propsito general como Quicksort que se usan con mayor frecuencia debido a su adaptabilidad a una mayor variedad de aplicaciones.
En algunas aplicaciones a la medida, el ordenamiento por radix puede ejecutarse hasta en el doble de velocidad que Quicksort, pero no vale la pena intentarlo si existe problemas potenciales de espacio de almacenamiento o si las llaves son de tamao variable y/o no son aleatorias.
VENTAJAS El ordenamiento es razonablemente eficiente si el nmero de dgitos en las llaves no es demasiado grande. Si las mquinas tienen la ventaja de ordenar los dgitos (sobre todo si estn en binario) lo ejecutaran con mucho mayor rapidez de lo que ejecutan una MTODO DE ORDENAMIENTO RADIX SORT comparacin de dos llaves completas.
1 5