Algoritmo de ordenamiento
Radix- Sort
Flores Wong Rosa Elena
Mendoza Ibarra Mayra
Ayala Inzunza Briseida
Estructura de Datos
Prof. Doc. Lucia Barrón
HISTORIA






EE.UU., 1880: no se puede terminar el censo de la década anterior (en
concreto, no se llega a contar el número de habitantes solteros)
– Herman Hollerith (empleado de la oficina del censo, de 20 años de edad)
inventa una máquina tabuladora eléctrica para resolver el problema; en
esencia es una implementación física del radix sort 1890: se usan unas
100 máquinas de Hollerith para tabular las listas del censo de la década (un
operador experto procesaba 19.071 tarjetas en una jornada laboral de 6’5
horas, unas 49 tarjetas por minuto)
– 1896: Hollerith crea la empresa Tabulating Machine Company 1900:
Hollerith resuelve otra crisis federal inventando una nueva máquina con
alimentación automática de tarjetas (útil, con más o menos variaciones, hasta
1960)
– 1911: la empresa de Hollerith se fusiona con otras dos, creando la
Calculating-Tabulating- Recording Company (CTR)
– 1924: Thomas Watson cambia el nombre a la CTR y la llama
International Business Machines (IBM) El resto de la historia es bien
conocido… hasta: – 2000: crisis del recuento de votos en las Presidenciales El
resto de la historia es bien conocido…
Radix Sort

Es un algoritmo de ordenamiento que
ordena enteros procesando sus dígitos
de forma individual. Como los enteros
pueden representar cadenas de
caracteres (por ejemplo, nombres o
fechas) y, especialmente, números en
punto flotante especialmente
formateados, radix sort no está
limitado sólo a los enteros.
Descripción


Este método se puede considerar como una
generalización de la clasificación por urnas.
Consiste en hacer diversos montones de
fichas, cada uno caracterizado por tener en
sus componentes un mismo digito (letra si
es alfabética) en la misma posición; estos
montones se recogen en orden ascendente
y se reparte en montones según el siguiente
digito de la clave.
Ejemplo
345, 721, 425, 572, 836, 467, 672, 194, 365,
236, 891, 746, 431, 834, 247, 529, 216, 389
Paso 1: atendiendo el digito de menor peso
(unidades);
216
431
365
746
891
672
834
425
236
247
389
721
572
194
345
836
467
529
1
2
4
5
6
7
9
Tomando los montones en orden, la secuencia de fichas quedarían:
721, 891, 431, 572, 672, 194, 834, 345, 425, 365, 836, 236,
746, 216, 467, 347, 529, 389.
Paso 2: distribuimos las secuencia de fichas en
montones respecto al segundo digito:
236
529
836
247
425
834
746
467
672
216
721
431
345
365
572
389
891
1
2
3
4
6
7
8
9
194
tomando de nuevo los montones en orden la
secuencia de fichas quedari asi:
216
721
425
529
431
834
866
236
345
746
247
365
467
572
672
389
891
194
Continuación:
Paso 3: se distribuye de nuevo las fichas respecto
al tercer digito:
247
389
467
891
236
365
431
572
194
216
345
425
529
1
2
3
4
5
746
836
672
721
834
6
7
8
tomando de nuevo los montones en orden la
secuencia de fichas queda ya ordenada:
194
216
236
247
345
365
389
425
431
467
529
572
672
721
746
834
836
891
Clasificación




el de dígito menos significativo (LSD)
el de dígito más significativo (MSD).
Radix sort LSD procesa las
representaciones de enteros empezando por
el dígito menos significativo y moviéndose
hacia el dígito más significativo.
Radix sort MSD trabaja en sentido
contrario.
Radix sort MSD
"b, c, d, e, f, g, h, i, j, ba"
Ordenada
"b, ba, c, d, e, f, g, h, i, j"
Ej.2
1 al 10 será
"1, 10, 2, 3, 4, 5, 6, 7, 8, 9"
Radix sorts LSD
"1, 2, 3, 4, 5, 6, 7, 8, 9, 10".
Ejemplo
Vector original:
25 57 48 37 12 92 86 33
Asignamos los elementos en colas basadas en el dígito menos significativo de cada uno de ellos.
0:
1:
2: 12 92
3: 33
4:
5: 25
6: 86
7: 57 37
8: 48
9:
Después de la primera pasada, la ordenación queda:
12 92 33 25 86 57 37 48
Colas basadas en el dígito más significativo.
0:
1: 12
2: 25
3: 33 37
4: 485: 57
6:
7:
8: 86
9: 92
Lista ordenada:
12 25 33 37 48 57 86 92
ORDENAMIENTO POR
RADIX

Estos métodos no comparan llaves;
sino que procesan y comparan
pedazos de llaves.
Estabilidad

Un algoritmo de ordenamiento se
considera estable si preserva el orden
relativo de llaves iguales en la
estructura de datos-.
Ejemplo

si queremos ordenar por calificación una
lista de asistencia que se encuentra
ordenada alfabéticamente, un algoritmo
estable produce una lista en la que los
estudiantes con el mismo grado se
mantienen ordenados alfabéticamente,
mientras que un algoritmo inestable no
dejará trazas del ordenamiento original. La
mayoría de los métodos básicos son
estables, pero la mayoría de los métodos
sofisticados no lo son.
Ordenamiento por radix
directo

Una variante al método de intercambio radix
consiste en examinar los bits de derecha a
izquierda. El método depende de que el
proceso de partición de un bit sea estable.
Por lo que el proceso de partición utilizado
en el algoritmo de intercambio radix no nos
sirve; el proceso de partición es como
ordenar una estructura con solo dos valores,
por lo que el algoritmo de distribución por
conteo nos sirve muy bien.
Análisis de eficiencia de los
ordenamientos por radix


Depende en que las llaves estén compuestas de bits aleatorios
en un orden aleatorio. Si esta condición no se cumple ocurre
una fuerte degradación en el desempeño de estos métodos.
Adicionalmente, requiere de espacio adicional para realizar los
intercambios.
Los algoritmos de ordenamiento basados en radix se
consideran como de propósito particular debido a que su
factibilidad depende de propiedades especiales de las llaves,
en contraste con algoritmos de propósito general como
Quicksort que se usan con mayor frecuencia debido a su
adaptabilidad a una mayor variedad de aplicaciones.
Nota:

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
tamaño variable y/o no son aleatorias.
Análisis del Método
Radix Sort
Suponemos que el vector “V” tiene n elementos.
Al ser el campo clave entero el numero urnas es
d=10. Además el numero de dijitos de que consta
el campo clave va ser k. Con estas premisas y
teniendo en cuenta los dos bucles anidados de que
consta el algoritmo principal, tenemos que el
tiempo de ejecución es O(k*n+K*d).
Si las claves se consideran como cadenas binarias de
longitud log(n) entonces K=log (n) y el método
Radix Sort tomará un tiempo de ejecución:
O(nlog n)

TIEMPO


3n
3n
(falta formula general)
Si 'la v' es una constante, la clase de raíz
toma el tiempo lineal, la O (n). Note sin
embargo que si todos los números en la
serie son diferentes entonces la v es al
menos la O (n), entonces la O (log (n)) pasa
son necesario, la O (nlog (n)) - el tiempo en
general.
ESPACIO

Si una serie temporal es usada, el
espacio de trabajo suplementario
usado es la O (n). Es posible hacen la
clasificación sobre cada posición de
dígito in situ y luego sólo la O (log (n))
el espacio es necesario para guardar la
pista de las secciones de serie aún
para ser procesado, recurrentemente o
sobre un montón explícito
Código
public class radixSort {
public int [][] cam(int[]arr){
if(arr.length == 0)
return null;
int[][] np =
new int[arr.length][2]; //matrice
int[] q = new int[256];
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 = ((255<<(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<256;i++)
for(l=q[i];l!=-1;l=np[l][1])
arr[j++] = np[l][0];
return np;
Prueba
public class Prueba {
public static void main (String[] args) {
radixSort rs=new radixSort();
int [] a={10,20,30,40,50,60,70,80,90,12};
System.out.println(rs.cam(a));
}
}
Descargar

Algotitmo de ordenamiento arreglado