Método De Ordenamiento Base RADIX

Métodos De Ordenamiento Por Distribución

Método De Ordenamiento Base RADIX

                                Descripción

Este algoritmo está basado en los valores  reales de  los dígitos  de acuerdo a la posición que ocupan los  números que  son  ordenados.  Para  cada dígito de las cifras a ordenar se efectúan  los  siguientes pasos, comenzando con el dígito menos significativo y  terminando con el dígito más significativo.  Se toma  cada número  en el orden  original y se coloca en una de las 10 colas dependiendo  del  valor  del  dígito que  se  esté procesando, después comenzando con la cola de los números con dígitos  0 y  terminando con los de dígito 9 se regresan al arreglo original. Cuando se efectúa este proceso para cada dígito  al arreglo  está ordenado.  M es el número de dígitos que forman las cifras a ordenar.

                              Algoritmo

Inicio

ArregloRadix A[], n, d)

para i 1 hasta <=d i--

A=CountingShort (A, n, 10,i)

Fin RadixShort 

CountingShort (A[ ], n, k,digit)

C[ ] =0

PARA J = 1 HASTA J<=N j++

C[ A[j][digit]]

PARA k = 2 HASTA k<=N j++

C[i]+=C[i - 1]

para j=n hasta >=1 j--

e=A[j][digit]

B[C[e]]= A[j]

C[e] --

RETORNAR B

Fin CountingShort

                                   Código:

public class Radix 

//Se declara la funcion principal del metodo 

{ void Radix (int[] arr)

{ 

//Si el arreglo se inica en cero//

if(arr.length==0)

return;

//Se declaran los arreglos y se le asignan los valores//

int[][] np = new int[arr.length][2];

int[] q = new int[0x100];

int i,j,k,l,f =0;

//Se inicia su tamaño en cero hasta cuatro//

for(k=0;k<4;k++)

{ 

//Se inicia con el elemento que este mas a la izquierda //

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];

} 

void main(String[] args)

{ 

//Función que me muestra el arreglo ordenado //

int i;

int[] arr = new int[15]; 

System.out.print("original: "); 

for(i=0;i<arr.length;i++)

{ 

//Funcion de arreglos aleatorios //

arr[i]=(int)(Math.random()*1024); 

System.out.print(arr[i]+" "); 

} 

Radix (arr); 

System.out.print("\nordenados: "); 

for(i=0;i<arr.length;i++) 

System.out.print(arr[i]+" "); 

System.out.println("\nHecho."); 

}

}