Ordenamiento Radix

Ordenamiento de distribución por conteo

Un problema que se presenta con frecuencia es el siguiente: “Ordenar un archivo con N registros cuyas llaves son enteros comprendidos entre 0 y M-1”. Si M no es muy grande, se puede usar el algoritmo de distribución por conteo. La idea básica es contar el número de veces que se repite cada llave diferente y en una segunda pasada utilizar el conteo para posicionar los registros en el archivo.

void distributioncounting (itemType a[], int N, int M)
{
itemType *b;
b = new itemType [N];
int *count;
count = new int[M];
int i, j;
for (j = 0; j < M; j++) count [j] = 0;
for (i = 1; i <= N; i++) count [a] ++;
for (j = 1; j < M; j++) count [j] += count[j - 1];
for (i = N; i >= 1; i--) b[count[a]--] = a ;
for (i = 1; i <= N; i++) a = b;
delete b;
delete count;
}

Definición

En muchas aplicaciones se puede aprovechar el hecho de que las llaves se pueden representar como números dentro de un rango restringido. Se denominan ordenamientos radix a los métodos que sacan ventaja de las propiedades digitales de estos números. Estos métodos no comparan llaves; sino que procesan y comparan pedazos de llaves.

Los algoritmos de ordenamiento radix trabajan sobre dígitos individuales de los números que representan a las llaves cuando estas pertenecen a un sistema numérico base M (el radix). Muchas aplicaciones de ordenamiento pueden operar en llaves compuestas de números binarios.

Ordenamiento por intercambio radix.

Este algoritmo se basa en ordenar las llaves de forma tal que todas las que inicien con un bit en 0 aparezcan antes que todas las que inicien con un bit en 1 y proceder sucesivamente con el resto de los bits mientras queden elementos pendientes de ordenar. Esto da lugar a un algoritmo recursivo. Para reordenar el arreglo inspeccionar comenzando por la izquierda hasta encontrar una llave que empiece con un bit en 1, después inspeccionar por la derecha hasta encontrar una llave que empiece con un bit en 0, intercambiar las llaves y continuar hasta que se crucen los apuntadores de ambas inspecciones.

void radixexchange (itemType a[], int left, int right, int bit)
{
int i, j; itemType t;
if (right > left && bit >= 0)
{
i = left; j = right;
while (j != i)
{
while (!a.bits (bit, 1) && i < j) i++;
while ( a[j].bits (bit, 1) && j > i) j--;
swap (a, i, j);
}
if (!a[right].bits (bit, 1)) j++;
radixexchange (a, left, j - 1, bit - 1);
radixexchange (a, j, right, bit - 1);
}
}

Este método se emplea para organizar información por mas de un criterio. Lo que hacemos es determinar la importancia de los criterios de ordenación y aplicar ordenación estable tantas veces como criterios se tengan, empezando por el criterio menos importante y determinando por el criterio más importante.

Estabilidad

Un algoritmo de ordenamiento se considera estable si preserva el orden relativo de llaves iguales en la estructura de datos. Por 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. Si asumimos que M = 2 en el algoritmo de distribución por conteo y reemplazamos a por bits (a, k, 1) podemos ordenar el arreglo a en sus k posiciones menos significativas usando un arreglo temporal b. Pero nos conviene más usar un valor de M mayor que corresponda a m bits a la vez durante el ordenamiento con M = 2m como en el siguiente código.

void straightradix (itemType a[], itemType b[], int N)
{
int i, j, pass, count [M-1];
for (pass = 0; pass < numBits / m; pass++)
{
for (j=0; j < M; j++) count [j] = 0;
for (i = 1; i <= N; i++)
count [a .bits (pass * m, m)]++;
for (j = 1; j < M; j++)
count [j] += count [j - 1];
for (i = N; i >= 1; i--)
b [count [a .bits (pass * m, m)] --] = a ;
for (i = 1; i <= N; i++) a = b;
}
}

Aplicación

Creamos primero nuestra forma de la siguiente manera:

:estructura_datos_csharp_develop:radix_3.jpg

Ahora implementamos el siguiente código en el botón Ordenamiento Radix:

	public void RadixSort(int[] a)
	{  
	   // Este es nuestro arreglo auxiliar .
	   int[] t=new int[a.Length]; 
	    
	   // Tamaño en bits de nuestro grupo. 
	    // Intenta también 2, 8 o 16 para ver si es rápido o no.
	   int r=2;  
	    
	   // Número de bits de un entero en c#. 
	   int b=32; 
	    
	   // Inicia el conteo a asignación de los arreglos.
	   // Notar dimensiones 2^r el cual es el número de todos los valores posibles de un número r-bit.
	   int[] count=new int[1<<r]; 
	   int[] pref=new int[1<<r]; 
	    
	   // Número de grupos. 
	   int groups=(int)Math.Ceiling((double)b/(double)r); 
	    
	   // Máscara para identificar los grupos.
	   int mask = (1<<r)-1; 
	    
	   // Implementación del algoritmo 
	   for (int c=0, shift=0; c<groups; c++, shift+=r)
	    { 
	       // Reiniciar el conteo en los arreglos.
	       for (int j=0; j<count.Length; j++)
	           count[j]=0;
	
	       // Contar elementos del c-vo grupo.
	       for (int i=0; i<a.Length; i++)
	           count[(a[i]>>shift)&mask]++; 
	
	       // Calculando prefijos.
	       pref[0]=0; 
	       for (int i=1; i<count.Length; i++)
	           pref[i]=pref[i-1]+count[i-1]; 
	
	       // De a[] a t[] elementos ordenados por c-vo grupo .
	       for (int i=0; i<a.Length; i++)
	           t[pref[(a[i]>>shift)&mask]++]=a[i]; 
	
	       // a[]=t[] e inicia otra vez hasta el último grupo. 
	       t.CopyTo(a,0); 
	       
	       Console.WriteLine("{0}",c);
	    } 
	   // Está ordenado 	   
	}

Ejecutando el programa:

:estructura_datos_csharp_develop:radix_1.jpg

O bien en consola insertar el código:

using System;
using System.Collections.Generic;
namespace RadixSort
{
	class Radix
	{
	public void RadixSort(int[] a)
	{  
	   // Este es nuestro arreglo auxiliar .
	   int[] t=new int[a.Length]; 
	    
	   // Tamaño en bits de nuestro grupo. 
	    // Intenta también 2, 8 o 16 para ver si es rápido o no.
	   int r=2;  
	    
	   // Número de bits de un entero en c#. 
	   int b=32; 
	    
	   // Inicia el conteo a asignación de los arreglos.
	    // Notar dimensiones 2^r el cual es el número de todos los valores posibles de un número r-bit.
	   int[] count=new int[1<<r]; 
	   int[] pref=new int[1<<r]; 
	    
	   // Número de grupos. 
	   int groups=(int)Math.Ceiling((double)b/(double)r); 
	    
	   // Máscara para identificar los grupos.
	   int mask = (1<<r)-1; 
	    
	   // Implementación del algoritmo 
	   for (int c=0, shift=0; c<groups; c++, shift+=r)
	    { 
	       // Reiniciar el conteo en los arreglos.
	       for (int j=0; j<count.Length; j++)
	           count[j]=0;
	
	       // Contar elementos del c-vo grupo.
	       for (int i=0; i<a.Length; i++)
	           count[(a[i]>>shift)&mask]++; 
	
	       // Calculando prefijos.
	       pref[0]=0; 
	       for (int i=1; i<count.Length; i++)
	           pref[i]=pref[i-1]+count[i-1]; 
	
	       // De a[] a t[] elementos ordenados por c-vo grupo .
	       for (int i=0; i<a.Length; i++)
	           t[pref[(a[i]>>shift)&mask]++]=a[i]; 
	
	       // a[]=t[] e inicia otra vez hasta el último grupo. 
	       t.CopyTo(a,0); 
	       
	       Console.WriteLine("{0}",c);
	    } 
	   // Está ordenado 	   
	}
		
		public static void Main(string[] args)
		{
			int[] a = new int[7] {2,3,1,0,5,6,9};
			
			Console.WriteLine("Ordenamiento Radix");
			
			Radix O = new Radix();			
			O.RadixSort(a);
			
			Console.ReadLine();
		}
	}
}

Y obtendremos:

:estructura_datos_csharp_develop:radix_2.jpg

Análisis de eficiencia de los ordenamientos por radix

La eficiencia de este algoritmo 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.

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 tamaño variable y/o no son aleatorias.

 


 


Driven by DokuWiki

Politica de Privacidad