BotonMenu
BotonIndice

PASCAL CON FREE PASCAL

PASCAL CON FREE PASCAL

PASCAL CON FREE PASCAL


8. ALGORITMOS DE ORDENACIÓN Y BUSQUEDA.
8.5. ORDENAMIENTO POR BASES. (RADIX SORT)
8. ALGORITMOS DE ORDENACIÓN Y BUSQUEDA.
8.5. ORDENAMIENTO POR BASES. (RADIX SORT)
8. ALGORITMOS DE ORDENACIÓN Y BUSQUEDA.
8.5. ORDENAMIENTO POR BASES. (RADIX SORT)

SIGUIENTE

SIGUIENTE

SIGUIENTE


‒ Ordenamiento por bases. (Radix sort)

El algoritmo de Ordenamiento por bases o Radix Sort, consiste en ordenar los números tomando en cuenta el valor relativo que tienen las cifras o dígitos de un número en un determinado sistema de numeración. La característica de este algoritmo está en que no hace comparaciones para ordenar las listas, simplemente se encarga de ir contando o agrupando los números que tengan el mismo valor relativo en determinada cifra. Se pueden ir agrupando o contando los números, desde las cifras menos significativas a las más significativas (LSD) ó en sentido contrario (MSD). El conteo o agrupación de los números se hace tomando en cuenta la base del sistema de numeración que se elija para ordenar (radix significa base).

Explicare como ordenar los siguientes números por agrupación desde las cifras menos significativas a las más significativas (LSD) en el sistema de numeración hexadecimal. Los números son: 456, 2689, 1025, 412, 482, 375 en hexadecimal serán: 1C8, A81, 401, 19C, 1E2, 177.

El método consiste en ir contando la cantidad de veces que aparece un número con determinada cifra para luego acumular los contadores y obtener la nueva posición de los números a ordenar.

Contando por la 1era cifra, la menos significativa: 1C8, A81, 401, 19C, 1E2, 177

Conteo. 1 --> 2 números
2 --> 1 número
7 --> 1 número
8 --> 1 número
C --> 1 número
Acumulación
del conteo.
1 --> 2
2 --> 3
7 --> 4
8 --> 5
C --> 6
Posiciones. 1 --> 1-0
2 --> 2
7 --> 3
8 --> 4
C --> 5
Los números se toman de derecha a izquierda. El 177 se coloca en la posición 3, el 1E2, en la posición 2, el 19C en la posición 5, el 401 en la posición 1, el A81 en la posición 0, y el 1C8 en la posición 4.
A81 401 1E2 177 1C8 19C
0 1 2 3 4 5

Contando por la 2da cifra: A81 ,401 ,1E2 ,177 ,1C8 ,19C

Conteo. 0 --> 1 número
7 --> 1 número
8 --> 1 número
9 --> 1 número
C --> 1 número
E --> 1 número
Acumulación
del conteo.
0 --> 1
7 --> 2
8 --> 3
9 --> 4
C --> 5
E --> 6
Posiciones. 0 --> 0
7 --> 1
8 --> 2
9 --> 3
C --> 4
E --> 5
Los números se toman de derecha a izquierda. El 19C se coloca en la posición 3, el 1C8 en la posición 4, y así sucesivamente.
401 177 A81 19C 1C8 1E2
0 1 2 3 4 5

Contando por la 3ra cifra: 401, 177, A81, 19C, 1C8, 1E2

Conteo. 1 --> 4 números
4 --> 1 número
A --> 1 número
Acumulación
del conteo.
1 --> 4
4 --> 5
A --> 6
Posiciones. 1 --> 3-2-1-0
4 --> 4
A --> 5
Los números se toman de derecha a izquierda. El 19C se coloca en la posición 3, el 1C8 en la posición 4, y así sucesivamente.
177 19C 1C8 1E2 401 A81
0 1 2 3 4 5

Para la implementación de este algoritmo no usaremos un sistema de numeración hexadecimal, en su defecto se podría decir que usaremos un sistema de numeración en base 255, la razón es que cuanto más grande sea el sistema de numeración o mejor dicho cuanto más grande sea el arreglo que almacene el conteo y las posiciones de los números, el algoritmo será más rápido. Para el conteo y obtención de las posiciones usaremos un arreglo identificado con el nombre pos de 256 números de tipo Longword, la implementación constará de un procedimiento que se encargará de Contar y Posicionar los números de la lista.


Descargar
Procedure OrdenarA(var A:LNaturales;n:byte);


 Procedure ContarPosicionar(A,B:LNaturales;i:longint);


 Var j:longint;
     d:byte;
     pos:array [0..255] of longword; //para contar y obtener las posiciones
 Begin

  FillDWord(pos,256,0);  //reinicia a 0


  for j:=low(A) to high(A) do  
    Begin	
    //permite obtener el byte
    d:=(A[j] shr ((8*i)-8)) and $FF;   
    //contador
    pos[d]:=pos[d]+1                           
  End;   


  // acumula las cuentas para obtener las posiciones
  for j:=0 to 254 do pos[j+1]:=pos[j]+pos[j+1];	


  for j:=high(A) downto low(A) do  //ascendente
    Begin		  		 	     		      
     //permite obtener el byte  para ubicarlo en la posicion correcta 
     d:=(A[j] shr ((8*i)-8)) and $FF;  
     pos[d]:=pos[d]-1;  //se decrementa la posicion		       
     B[pos[d]]:=A[j];    //se coloca en nueva posicion
    End;     
 End;
 
Var i:longint;       
    B:LNaturales; // arreglo dinamico auxiliar    
	     	     
Begin     
   SetLength(B,Length(A));


   for i:=1 to n do
     if (i mod 2)<>0
      then ContarPosicionar(A,B,i)   //se colocarán en B                             
      else ContarPosicionar(B,A,i);  //se colocarán en A  

   if  (n mod 2)<>0 then for i:=low(A) to  high(A) do A[i]:=B[i]
End;
Código fuente 10: Primer algortimo Radix sort.
Descargar

El Procedimiento empieza por crear un arreglo B auxiliar que permitirá ir colocando los números de la lista en su nueva posición, se usa este arreglo auxiliar debido a que no se puede ir colocando los números en el mismo arreglo, y el tamaño de este arreglo auxiliar será del mismo tamaño que el arreglo a ordenar. Debido a que LNaturales es un arreglo dinámico de tipo qword (8 bytes), entonces el proceso de contar y posicionar se realizará 8 veces, y el encargado de hacerlo será el bucle for, si no se usará el bucle for el proceso de contar y posicionar se tendría que haber realizado del siguiente modo:

ContarPosicionar(A,B,1); //Desde la cifra menos significativa o byte menos significativo
ContarPosicionar(B,A,2);
ContarPosicionar(A,B,3);
ContarPosicionar(B,A,4);
ContarPosicionar(A,B,5);
ContarPosicionar(B,A,6);
ContarPosicionar(A,B,7);
ContarPosicionar(B,A,8); //Hasta la cifra más significativa o byte más significativo

El procedimiento ContarPosicionar es el encargado de contar y posicionar los números del arreglo A hacia el B y viceversa, el procedimiento ContarPosicionar lo primero que hace es inicializar el arreglo pos. El Procedimiento ContarPosicionar está compuesto de tres bucles for, el primero se encarga de contar obteniendo el byte o cifra correspondiente, el segundo se encarga de acumular lo contado en el arreglo pos, el tercero se encarga de colocar el numero en la nueva posición restando en 1 cada vez que se obtiene la cifra o byte del numero a posicionar.

Para obtener un determinado byte hacemos uso de un enmascaramiento, por ejemplo si queremos obtener el byte 5 desplazamos el número 24 bits a la derecha y después hacemos una operación and con el número $FF, para quedarnos con el byte que estamos buscando, algo parecido a esto:

(A shr 0) and $FF --> para el byte menos significativo ó cifra menos significativa, byte 1
(A shr 8) and $FF --> byte 2
(A shr 16) and $FF --> byte 3
(A shr 24) and $FF --> byte 4
(A shr 32) and $FF --> byte 5
(A shr 40) and $FF --> byte 6
(A shr 48) and $FF --> byte 7
(A shr 56) and $FF --> para el byte más significativo o cifra más significativa, byte 8

Como se puede observar 0, 8, 16, 24 ... 56, son una progresión aritmética que se puede implementar con facilidad del siguiente modo:

d:=(A[j] shr ((8*i)-8) and $FF;

En caso queremos ordenar la lista ascendentemente o descendentemente se debe hacer un cambio dentro del procedimiento ContarPosicionar, es decir el 3er y último bucle for, se debe cambiar según sea el caso. Para un ordenamiento ascendente se debe usar:

for j:=high(A) downto low(A) do
 Begin
   d:=(A[j] shr ((8*i)-8)) and $FF;
   pos[d]:=pos[d]-1;
   B[pos[d]]:=A[j];
 End;

Y para un ordenamiento descendente se debe usar:

for j:=low(A) to high(A) do
 Begin
   d:=(A[j] shr ((8*i)-8)) and $FF;
   pos[d]:=pos[d]-1;
   B[high(B)-pos[d]]:=A[j];
 End;

Sucede a veces que los números de una lista no necesariamente ocuparán 8 bytes, por lo que el bucle for que ejecuta el procedimiento ContarPosicionar, se puede controlar con la variable n, es decir si sabemos que los números de la lista ocupan 5 bytes entonces se debe pasar el valor 5 en el parámetro n, del procedimiento.

Debido a que cada vez que se cuenta y posiciona los números estos se van intercambiando entre los arreglos A y B, cuando la cantidad de bytes de los números a ordenar es par, es decir es: 2, 4, 6, 8; la lista quedará ordenada en el arreglo original A, pero en caso sea impar, es decir: 1, 3, 5 y 7, la lista quedará ordenada en el arreglo auxiliar B, es por eso que al final del algoritmo se encuentra la siguiente condición if:

if (n mod 2)<>0 then for i:=low(A) to high(A) do A[i]:=B[i]

Cuando usamos el algoritmo con números positivos y negativos, y ordenamos la siguiente lista: 105, -110, 150, 125, -2, estos se ordenan del siguiente modo: 105, 125, 150, -110, -2 y para remediar este situación, una solución es convertir todos los números de la lista a números positivos, eso se logra obteniendo el complemento aritmético del número. Es decir a todos los números de la lista: 105, -110, 150, 125, -2, se le resta el menor número negativo -128, obteniendo la siguiente lista: 233, 18, 278, 253, 126, se ordena la lista: 18, 126, 233, 253, 278, y para recuperar los números originales se le suma el menor número negativo -128, y se obtiene la lista ordenada: -110, -2, 105, 125, 150. En el caso los números sean de 1 byte el menor número negativos será: -128=-1*(28/2), para un números de 2 bytes será: -32768=-1*(216/2), para números 3 bytes será: -8388608=-1*(224/2) y así sucesivamente. Con lo que el algoritmo quedaría del siguiente modo:


Descargar
Procedure OrdenarA(var A:LEnteros;n:byte);


 Procedure ContarPosicionar(A,B:LEnteros;i:longint);
 Var j:longint;
    d:byte;
    pos:array [0..255] of longword; //para contar y obtener las posiciones
 Begin
  FillDWord(pos,256,0);  //reinicia a 0


  for j:=low(A) to high(A) do  
    Begin	
    //permite obtener el byte
    d:=(A[j] shr ((8*i)-8)) and $FF;   
    //contador
    pos[d]:=pos[d]+1                           
  End;   


  // acumula las cuentas para obtener las posiciones
  for j:=0 to 254 do pos[j+1]:=pos[j]+pos[j+1];	


  for j:=high(A) downto low(A) do  //ascendente
    Begin		  		 	     		      
     //permite obtener el byte  para ubicarlo en la posicion correcta 
     d:=(A[j] shr ((8*i)-8)) and $FF;  
     pos[d]:=pos[d]-1;  //se decrementa la posicion		       
     B[pos[d]]:=A[j];    //se coloca en nueva posicion
    End;     
 End;
 
Var i:longint;       
    B:LNaturales; // arreglo dinamico auxiliar

	     	     
Begin     
   SetLength(B,Length(A));


   if (n=1) then for i:=low(A) to high(A) do A[i]:=A[i]+(-128);        
   if (n=2) then for i:=low(A) to high(A) do A[i]:=A[i]+(-32768);        
   if (n=3) then for i:=low(A) to high(A) do A[i]:=A[i]+(-8388608);        
   if (n=4) then for i:=low(A) to high(A) do A[i]:=A[i]+(-2147483648);        
   if (n=5) then for i:=low(A) to high(A) do A[i]:=A[i]+(-549755813888);        
   if (n=6) then for i:=low(A) to high(A) do A[i]:=A[i]+(-140737488355328);        
   if (n=7) then for i:=low(A) to high(A) do A[i]:=A[i]+(-36028797018963968);        
   if (n=8) then for i:=low(A) to high(A) do A[i]:=A[i]+(-9223372036854775808);        

    
   for i:=1 to n do
     if (i mod 2)<>0 
        then  ContarPosicionar(A,B,i)         //se colocarán en B                           
        else  ContarPosicionar(B,A,i);        //se colocarán en A 
           
   if  not(n mod 2)<>0 then for i:=low(A) to  high(A) do A[i]:=B[i];

   if (n=1) then for i:=low(A) to high(A) do A[i]:=A[i]-(-128);        
   if (n=2) then for i:=low(A) to high(A) do A[i]:=A[i]-(-32768);        
   if (n=3) then for i:=low(A) to high(A) do A[i]:=A[i]-(-8388608);        
   if (n=4) then for i:=low(A) to high(A) do A[i]:=A[i]-(-2147483648);        
   if (n=5) then for i:=low(A) to high(A) do A[i]:=A[i]-(-549755813888);        
   if (n=6) then for i:=low(A) to high(A) do A[i]:=A[i]-(-140737488355328);        
   if (n=7) then for i:=low(A) to high(A) do A[i]:=A[i]-(-36028797018963968);        
   if (n=8) then for i:=low(A) to high(A) do A[i]:=A[i]-(-9223372036854775808); 
End;
Código fuente 11: Algoritmo Radix Sort para números positivos y negativos.
Descargar

Cuando usamos el algoritmo con números reales positivos y negativos, el comportamiento es similar a como ordenar números enteros positivos y negativos, es decir si ordenamos la siguiente lista: 10.89, -11.5, 15.0, 1.25, -2.8, estos se ordenarán del siguiente modo: 1.25, 10.89, 15.0, -11.5, -2.8 y para remediar esta situación debemos convertir los números positivos a negativos e invertir todos los bits de los números negativos. Con lo que el algoritmo quedaría del siguiente modo:


Descargar
Procedure OrdenarA(var A:LReales);  


Procedure ContarPosicionar(A,B:LReales;i:longint);
 Var j:longint;              
    d:byte;
    pos:array [0..255] of longword;	
 Begin
   FillDWord(pos,256,0);  
   for j:=low(A) to high(A) do  
        Begin
          d:=(qword(A[j]) shr ((8*i)-8)) and $FF;
          pos[d]:=pos[d]+1
        End;
   for j:=0 to 254 do pos[j+1]:=pos[j]+pos[j+1];
   for j:=high(A) downto low(A) do
       Begin
         d:=(qword(A[j]) shr ((8*i)-8)) and $FF;	
         pos[d]:=pos[d]-1;  
         B[pos[d]]:=A[j];    		       
       End;
 End;
 
Var i:longint;       
    B:LReales;    

Begin     
   SetLength(B,Length(A));    
   
   for i:=low(A) to high(A) do

      if (A[i]<0) then qword(A[i]):=not(qword(A[i]))
                  else A[i]:=A[i]*-1;
 
   for i:=1 to 8 do
     if (i mod 2)<>0 
       then ContarPosicionar(A,B,i)
       else ContarPosicionar(B,A,i);

   for i:=low(A) to high(A) do  
      if (A[i]<0) then A[i]:=A[i]*-1
                  else qword(A[i]):=not(qword(A[i]))
End;
Código fuente 12: Algoritmo Radix Sort para números reales positivos y negativos..
Descargar

Los números reales de la lista siempre serán de 8 bytes, si queremos usar este algoritmo con un tipo de dato como el single (4 bytes), entonces se debe adaptar el procedimiento, haciendo cambios en el bucle for que ejecuta el procedimiento ContarPosicionar y en la obtención del byte o cifra de los números reales a ordenar.

La implementación de este algoritmo con una lista de cadena de caracteres, es realmente más sencillo pero su rendimiento es ineficiente cuando la longitud de las cadenas de caracteres sobrepase los 18 caracteres (sólo en Unicodestring). El siguiente procedimiento implementa el algoritmo para su uso con LPalabras:


Descargar
Procedure OrdenarA(var A:LPalabras;n:byte);


Procedure ContarPosicionar(A,B:LPalabras;i:longint);
Var j:longint;
      d:word;
      pos:array [64..90] of longword;
Begin
   FillDWord(pos,27,0);


   for j:=low(A) to high(A) do  
    Begin
      if i>length(A[j])
        then d:=64
        else d:=Word(A[j,i]);
      pos[d]:=pos[d]+1
    End;

   for j:=64 to 89 do pos[j+1]:=pos[j]+pos[j+1];

   for j:=high(A) downto low(A) do
       Begin
         if i>length(A[j])
          then d:=64
          else d:=Word(A[j,i]);
         pos[d]:=pos[d]-1;
         B[pos[d]]:=A[j];
       End;
End;

Var i:longint;
    B:LPalabras;
Begin
   SetLength(B,Length(A));   
   for i:=n downto 1 do
        if (i mod 2)=0 
           then  ContarPosicionar(A,B,i) 
           else  ContarPosicionar(B,A,i);
   if  (n mod 2)<>0 then for i:=low(A) to  high(A) do A[i]:=B[i]
End;
Código fuente 13: Algoritmo Radix Sort para cadena de caracteres.
Descargar

Para obtener los caracteres simplemente se acceden de derecha a izquierda o de atrás hacia adelante, este procedimiento está diseñado sólo para ordenar palabras en mayúsculas compuestas por caracteres del alfabeto en latín. Es por eso que el arreglo pos sólo va desde 64 hasta 90, cubriendo 27 caracteres empezando e incluyendo el carácter @. Debido a que las cadenas de caracteres son de longitud variable, cuando se intente acceder a un carácter por la derecha que no existe, entonces el algoritmo debe considerarlo como un carácter @, esto es mejor que rellenar las cadenas de caracteres de @ para que todos tengan la misma longitud.

El siguiente archivo comprimido: OrdenacionPorBases.zip, tiene 4 programas de ejemplo para los tipos de datos LNaturales, LEnteros, LReales, LPalabras de la unidad listas.




SIGUIENTE
SIGUIENTE
SIGUIENTE


 
‒ Comentarios y sugerencias.

Agradezco de antemano, todo comentario, sugerencia, y donativo (a través de Paypal me), que ayude a mejorar los contenidos educativos de Conoce 3000. Además, cualquier pregunta o duda que tengas lo puedes hacer por este medio. Pero, todo contenido que pueda resultar ofensivo, malicioso, racista, sexista, discriminatorio, obsceno, vulgar será eliminado.








PORTADA |  INTERESANTE |  APUNTES |  LIBROS |  GALERIA


Creative Commons License


Todos los textos, imágenes y videos de Conoce3000 estan colocados bajo una licencia : Creative Commons Reconocimiento-NoComercial 3.0 Unported License.