Estructura de Datos : Clasificación Radix

Definiciones

Base de un sistema de numeración.

Radix significa en inglés raíz o base de un sistema de numeración.
Ejemplo en el sistema de numeración decimal.
- Una clave interpretada según el sistema de numeración decimal en el rango de 000 =< K =< 999.
  - K1 - El dígito de los cientos - 0 =< K1 =< 9
  - K2 - El dígito de las decenas - 0 =< K2 =< 9
  - K3 - El dígito de las unidades - 0 =< K3 =< 9
Este ejemplo tiene 3 digitos decimales. El número de bins requeridos es 10, de 0 a 9. El número de pasadas requeridas es 3. El método de clasificación se llama clasificación de base 10 ( radix 10 sort ).
Ejemplo en el sistema de numeración binario.
- Una clave interpretada según el sistema de numeración binario en el rango de 00000000 =< K =< 11111111.
  - K1 - El dígito de la posición 1 - 0 =< K1 =< 1
  - K2 - El dígito de la posición 2 - 0 =< K2 =< 1
  - K3 - El dígito de la posición 3 - 0 =< K3 =< 1
  - K4 - El dígito de la posición 4 - 0 =< K4 =< 1
  - K5 - El dígito de la posición 5 - 0 =< K5 =< 1
  - K6 - El dígito de la posición 6 - 0 =< K6 =< 1
  - K7 - El dígito de la posición 7 - 0 =< K7 =< 1
  - K8 - El dígito de la posición 8 - 0 =< K8 =< 1
Este ejemplo tiene 8 digitos binarios. El número de bins requeridos es 2, de 0 a 1. El número de pasadas requeridas es 8. El método de clasificación se llama clasificación de base 2 ( radix 2 sort ).
Ejemplo en el sistema de numeración de base r.
- Una clave interpretada según el sistema de numeración de base r en el rango de 0000 =< K =< (r-1)(r-1)(r-1)(r-1).
  - K1 - El dígito de la posición 1 - 0 =< K1 =< r-1
  - K2 - El dígito de la posición 2 - 0 =< K2 =< r-1
  - K3 - El dígito de la posición 3 - 0 =< K3 =< r-1
  - K4 - El dígito de la posición 4 - 0 =< K4 =< r-1
Este ejemplo tiene 4 digitos de base r. El número de bins requeridos es r, de 0 a r-1. El número de pasadas requeridas es 4. El método de clasificación se llama clasificación de base r ( radix r sort ).

Las condiciones iniciales son las siguientes :

El archivo a clasificar ya está en memoria, dispuesto en slots contiguos.
Los registros del archivo los denominaremos R1, R2, R3, ..., Ri, ..., Rn donde 1=< i =< n.
Existen en memoria n slots, donde en cada uno de ellos se dispone un registro del archivo a clasificar.
Todos los registros tienen claves Ki, Ki, ..., Ki donde i es 1 =< i =< n.
Las claves de los registros se consideran partidas o con multiples claves. Cada parte de la clave es un digito de la misma. Por lo tanto, la interpretacion de claves partidas es la del siguiente punto.
Todos los registros tienen claves Ki1, Ki2, ..., Kid donde i es 1 =< i =< n.
Los registros están desordenados respecto de las claves mencionadas.

Los registros tienen un campo de enlace usado para unir en una lista enlazada simple todos los registros.

 R1             R2             R3             R4             R5             R6             R7             R8             R9             R10
+---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+
|     | *-|--->|     | *-|--->|     | *-|--->|     | *-|--->|     | *-|--->|     | *-|--->|     | *-|--->|     | *-|--->|     | *-|--->|     | 0 |      Lista  enlazada ( Archivo )
+---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+

La clasificación será hecha con la ayuda de un conjunto de r bins donde r es 1 =< i =< r.
Los bins son colas enlazadas simples con :
- Variables que apuntan al registro que está en el frente de cada cola y que denominaremos F(i) para 0 =< i =< r.
- Variables que apuntan al registro que está en el final de cada cola y que denominaremos E(i) para 0 =< i =< r.
Bins significa en inglés cajones, recipientes o compartimientos.

Esta clasificacion usa arreglos, listas enlazas y colas enlazadas.

     +---+          +---------+    +---------+                       +---------+          +---+
F(1) | *-|--------->|     | *-|--->|     | *-|--->..............---->|     | 0 |<---------|-* | E(1)    Cola enlazada ( Bin 1 )
     +---+          +---------+    +---------+                       +---------+          +---+

     +---+          +---------+    +---------+                       +---------+          +---+
F(2) | *-|--------->|     | *-|--->|     | *-|--->..............---->|     | 0 |<---------|-* | E(2)    Cola enlazada ( Bin 2 )
     +---+          +---------+    +---------+                       +---------+          +---+

       .
       .
       .

     +---+          +---------+    +---------+                       +---------+          +---+
F(r) | *-|--------->|     | *-|--->|     | *-|--->..............---->|     | 0 |<---------|-* | E(3)    Cola enlazada ( Bin r )
     +---+          +---------+    +---------+                       +---------+          +---+

Como se ve son necesarios r bins.

La secuencia de acciones es la siguiente :

Ejemplos

Ejemplo 1

Archivo Inicial Desordenado

    R1             R2             R3             R4             R5             R6             R7             R8             R9             R10
   +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+
   | 179 | *-|--->| 208 | *-|--->| 306 | *-|--->|  93 | *-|--->| 859 | *-|--->| 984 | *-|--->|  55 | *-|--->|   9 | *-|--->| 271 | *-|--->|  33 | 0 |
   +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+

Primera Pasada por el Digito Menos Significativo

       E(0)           E(1)           E(2)           E(3)           E(4)           E(5)           E(6)           E(7)           E(8)           E(9)
        |              |              |              |              |              |              |              |              |              |
        |              |              |              |              |              |              |              |              |              V
        |              |              |              |              |              |              |              |              |           +-----+
        |              |              |              |              |              |              |              |              |           |   9 |
        |              |              |              |              |              |              |              |              |           +-----+
        |              |              |              |              |              |              |              |              |              A
        |              |              |              |              |              |              |              |              |              |
        |              |              |              V              |              |              |              |              |              |
        |              |              |           +-----+           |              |              |              |              |           +-----+
        |              |              |           |  33 |           |              |              |              |              |           | 859 |
        |              |              |           +-----+           |              |              |              |              |           +-----+
        |              |              |              A              |              |              |              |              |              A
        |              |              |              |              |              |              |              |              |              |
        |              V              |              |              V              V              V              |              V              |
        |           +-----+           |           +-----+        +-----+        +-----+        +-----+           |           +-----+        +-----+
        |           | 271 |           |           |  93 |        | 984 |        |  55 |        | 306 |           |           | 208 |        | 179 |
        |           +-----+           |           +-----+        +-----+        +-----+        +-----+           |           +-----+        +-----+
        |              A              |              A              A              A              A              |              A              A
        V              |              V              |              |              |              |              V              |              |
       F(0)           F(1)           F(2)           F(3)           F(4)           F(5)           F(6)           F(7)           F(8)           F(9)

Archivo Primera Pasada

    R1             R2             R3             R4             R5             R6             R7             R8             R9             R10
   +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+
   | 271 | *-|--->|  93 | *-|--->|  33 | *-|--->| 984 | *-|--->|  55 | *-|--->| 306 | *-|--->| 208 | *-|--->| 179 | *-|--->| 859 | *-|--->|   9 | 0 |
   +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+

Segunda Pasada por el Digito Intermedio

       E(0)           E(1)           E(2)           E(3)           E(4)           E(5)           E(6)           E(7)           E(8)           E(9)
        |              |              |              |              |              |              |              |              |              |
        V              |              |              |              |              |              |              |              |              |
     +-----+           |              |              |              |              |              |              |              |              |
     |   9 |           |              |              |              |              |              |              |              |              |
     +-----+           |              |              |              |              |              |              |              |              |
        A              |              |              |              |              |              |              |              |              |
        |              |              |              |              |              |              |              |              |              |
        |              |              |              |              |              V              |              V              |              |
     +-----+           |              |              |              |           +-----+           |           +-----+           |              |
     | 208 |           |              |              |              |           | 859 |           |           | 179 |           |              |
     +-----+           |              |              |              |           +-----+           |           +-----+           |              |
        A              |              |              |              |              A              |              A              |              |
        |              |              |              |              |              |              |              |              |              |
        |              |              |              V              |              |              |              |              V              V
     +-----+           |              |           +-----+           |           +-----+           |           +-----+        +-----+        +-----+
     | 306 |           |              |           |  33 |           |           |  55 |           |           | 271 |        | 984 |        |  93 |
     +-----+           |              |           +-----+           |           +-----+           |           +-----+        +-----+        +-----+
        A              |              |              A              |              A              |              |              A              A
        |              V              V              |              V              |              V              V              |              |
       F(0)           F(1)           F(2)           F(3)           F(4)           F(5)           F(6)           F(7)           F(8)           F(9)

Archivo Segunda Pasada

    R1             R2             R3             R4             R5             R6             R7             R8             R9             R10
   +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+
   | 306 | *-|--->| 208 | *-|--->|   9 | *-|--->|  33 | *-|--->|  55 | *-|--->| 859 | *-|--->| 271 | *-|--->| 179 | *-|--->| 984 | *-|--->|  93 | 0 |
   +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+

Tercera Pasada por el Digito Mas Significativo

       E(0)           E(1)           E(2)           E(3)           E(4)           E(5)           E(6)           E(7)           E(8)           E(9)
        |              |              |              |              |              |              |              |              |              |
        V              |              |              |              |              |              |              |              |              |
     +-----+           |              |              |              |              |              |              |              |              |
     |  93 |           |              |              |              |              |              |              |              |              |
     +-----+           |              |              |              |              |              |              |              |              |
        A              |              |              |              |              |              |              |              |              |
        |              |              |              |              |              |              |              |              |              |
     +-----+           |              |              |              |              |              |              |              |              |
     |  55 |           |              |              |              |              |              |              |              |              |
     +-----+           |              |              |              |              |              |              |              |              |
        A              |              |              |              |              |              |              |              |              |
        |              |              |              |              |              |              |              |              |              |
        |              |              V              |              |              |              |              |              |              |
     +-----+           |           +-----+           |              |              |              |              |              |              |
     |  33 |           |           | 271 |           |              |              |              |              |              |              |
     +-----+           |           +-----+           |              |              |              |              |              |              |
        A              |              A              |              |              |              |              |              |              |
        |              |              |              |              |              |              |              |              |              |
        |              V              |              V              |              |              |              |              V              V
     +-----+        +-----+        +-----+        +-----+           |              |              |              |           +-----+        +-----+
     |   9 |        | 179 |        | 208 |        | 306 |           |              |              |              |           | 859 |        | 948 |
     +-----+        +-----+        +-----+        +-----+           |              |              |              |           +-----+        +-----+
        A              A              A              A              |              |              |              |              A              A
        |              |              |              |              V              V              V              V              |              |
       F(0)           F(1)           F(2)           F(3)           F(4)           F(5)           F(6)           F(7)           F(8)           F(9)

Archivo Final Ordenado

    R1             R2             R3             R4             R5             R6             R7             R8             R9             R10
   +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+
   |   9 | *-|--->|  33 | *-|--->|  55 | *-|--->|  93 | *-|--->| 179 | *-|--->| 208 | *-|--->| 271 | *-|--->| 306 | *-|--->| 859 | *-|--->| 948 | 0 |
   +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+    +---------+

Funciones

LRSORT ( LSD radix r )

Desarrollar la funcion en base a este esqueleto base.

procedure LRSORT(R, n, d)

declare
for
- do
  - for
    - do
    - end
  - while
    - do
    - end
  - j <---- 0
  - while
    - do
    - end
  - p <---- F(j)
  - t <---- E(j)
  - for
    - do
    - LINK(t) <---- 0
    - end
- end

end LRSORT