Ordenamiento Radix

Ordenamiento Radix Concepto: El ordenamiento Radix es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual

En informática, el ordenamiento Radix (radix sort en inglés) 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

La mayor parte de los ordenadores digitales representan internamente todos sus datos como representaciones electrónicas de números binarios, por lo que procesar los dígitos de las representaciones de enteros por representaciones de grupos de dígitos binarios es lo más conveniente. Existen dos clasificaciones de radix sort: el de dígito menos significativo (LSD) y 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.

Las representaciones de enteros que son procesadas por los algoritmos de ordenamiento se les llama a menudo "claves", que pueden existir por sí mismas o asociadas a otros datos. Radix sort LSD usa típicamente el siguiente orden: claves cortas aparecen antes que las claves largas, y claves de la misma longitud son ordenadas de forma léxica. Esto coincide con el orden normal de las representaciones de enteros, como la secuencia "1, 2, 3, 4, 5, 6, 7, 8, 9, 10". Radix sorts MSD usa orden léxico, que es ideal para la ordenación de cadenas de caracteres, como las palabras o representaciones de enteros de longitud fija. Una secuencia como "b, c, d, e, f, g, h, i, j, ba" será ordenada léxicamente como "b, ba, c, d, e, f, g, h, i, j". Si se usa orden léxico para ordenar representaciones de enteros de longitud variable, entonces la ordenación de las representaciones de los números del 1 al 10 será "1, 10, 2, 3, 4, 5, 6, 7, 8, 9", como si las claves más cortas estuvieran justificadas a la izquierda y rellenadas a la derecha con espacios en blanco, para hacerlas tan largas como la clave más larga, para el propósito de este ordenamiento.

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:48

5:57

6:

7:

8:86

9:92

Lista ordenada:

12 25 33 37 48 57 86 92

Implementaciones

El algoritmo Radix Sort en C

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define NUMELTS 20

void radixsort(int x[], int n)
{
  int front[10], rear[10];
  struct {
    int info;
    int next;
  } node[NUMELTS];
  int exp, first, i, j, k, p, q, y;

  /* Inicializar una lista vinculada */
  for (i = 0; i < n-1; i++) {
    node[i].info = x[i];
    node[i].next = i+1;
  } /* fin del for */
  node[n-1].info = x[n-1];
  node[n-1].next = -1;
  first = 0; /* first es la cabeza de la lista vinculada */
  for (k = 1; k < 5; k++) {
    /* Suponer que tenemos números de cuatro dígitos */
    for (i = 0; i < 10; i++) {
      /*Inicializar colas */
      rear[i] = -1;
      front[i] = -1;
    } /*fin del for */
    /* Procesar cada elemento en la lista */
    while (first != -1) {
      p = first;
      first = node[first].next;
      y = node[p].info;
      /* Extraer el kâsimo dÁgito */
      exp = pow(10, k-1);	/* elevar 10 a la (k-1)ésima potencia */
      j = (y/exp) % 10;
      /* Insertar y en queue[j] */
      q = rear[j];
      if (q == -1)
	front[j] = p;
      else
	node[q].next = p;
      rear[j] = p;
    } /*fin del while */

    /* En este punto, cada registro está en su cola basándose en el dígito k
       Ahora formar una lista única de todos los elementos de la cola.
       Encontrar el primer elemento. */
    for (j = 0; j < 10 && front[j] == -1; j++);
      ;
    first = front[j];

    /* Vincular las colas restantes */
    while (j <= 9) { 	/* Verificar si se ha terminado */
      /*Encontrar el elemento siguiente */
      for (i = j+1; i < 10 && front[i] == -1; i++);
	;
      if (i <= 9) {
	p = i;
	node[rear[j]].next = front[i];
      } /* fin del if */
      j = i;
    } /* fin del while */
    node[rear[p]].next = -1;
  } /* fin del for */

  /* Copiar de regreso al archivo original */
  for (i = 0; i < n; i++) {
    x[i] = node[first].info;
    first = node[first].next;
  } /*fin del for */
} /* fin de radixsort*/


int main(void)
{
  int x[50] = {NULL}, i;
  static int n;

  printf("\nCadena de números enteros: \n");
  for (n = 0;; n++)
    if (!scanf("%d", &x[n])) break;
  if (n)
    radixsort (x, n);
  for (i = 0; i < n; i++)
    printf("%d ", x[i]);
  return 0;
}

El algoritmo Radix Sort en Perl, para claves de igual longitud

sub radix_sort {
    my $array = shift;           # Recibimos una referencia a un array
    my $from  = $array;
    my $to;

    # Esperamos que todas las claves tengan la misma longitud,
    # por lo que hacemos un bucle por todos los dígitos, desde
    # el que está más a la derecha, hacia la izquierda
    for ( my $i = length $array->[ 0 ] - 1; $i >= 0; $i-- ) {

        # Una nueva lista de ordenación
        $to = [ ];

        # Para todas las claves a ordenar
        foreach my $clave ( @$from ) {

            # Estabilidad es esencial, por lo que usamos push().
            # $to es un array de referencias a arrays de claves ordenadas
            # según el valor numérico (ord()) del dígito de la clave
            push @{ $to->[ ord( substr $clave, $i ) ] }, $clave;
        }

        # Concatenamos todos los valores ordenados en un solo array.
        # Desplegamos los arrays dentro del array $to
        $from = [ map { @{ $_ || [ ] } } @$to ];
    }

    # Ahora copiamos los elementos al array original, como valor de retorno
    @$array = @$from;
}

Ventajas

• El ordenamiento es razonablemente eficiente si el número de dígitos en las llaves no es demasiado grande.
• Si las máquinas tienen la ventaja de ordenar los dígitos (sobre todo si están en binario) lo ejecutarían con mucho mayor rapidez de lo que ejecutan una comparación de dos llaves completas.

Fuentes

• Sort::Radix módulo Perl en CPAN
• Sort::Key::Radix módulo Perl en CPAN
• Radix Sort en Python Radix en Python
• Ordenamiento de raíz (radix sort)