Método de Ordenación Radix en C++

Hola amig@s para terminar la entrega de Métodos de ordenación lo haremos con el método Radix. 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.

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.

Imagen:

Código:

RadixSort.cpp:

#include "RadixSort.h"
void main(){
 RadixSort RS;
 RS.inicia();
}

RadixSort.h:

#include <iostream>
#include <windows.h>
#include <math.h>
using namespace std;
#define MAX 100

struct{
 int inf;
 int sig;
}nodo[MAX];

class RadixSort{
public:
 int vector[MAX], post[MAX],frente[MAX];
 void inicia(void);
 void radixSort(int[] ,int);
};

void RadixSort::inicia(){
 int n;
 cout<<"Ingrese el numeo de elementos que desea insertar: ";cin>>n;
 for(int i=0;i<n;i++){
  cout<<endl<<"Elemento["<<i+1<<"]: ";cin>>vector[i];
 }
 system("cls");
 cout<<endl<<endl<<"Elementos desordenados:"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<endl<<vector[i];
 }
 radixSort(vector,n);
 cout<<endl<<endl<<"Elementos ordenados por metodo Radix Sort:"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<endl<<vector[i];
 }
 system("pause>null");
}

void RadixSort::radixSort(int V[], int N){
 int exp, primero, p, q, y,j,i,k;
 for (int i = 0; i < N-1; i++) {
  nodo[i].inf = V[i];
  nodo[i].sig = i+1;
 }
 nodo[N-1].inf = V[N-1];
 nodo[N-1].sig = -1;
 primero = 0;
 for ( k = 1; k < 5; k++) {
  for ( i = 0; i < 10; i++) {
   post[i] = -1;
   frente[i] = -1;
  }

  while (primero != -1) {
   p = primero;
   primero = nodo[primero].sig;
   y = nodo[p].inf;
   exp = pow((double)10, k-1);
   j = (y/exp) % 10;
   q = post[j];
   if (q == -1)
    frente[j] = p;
   else
    nodo[q].sig = p;
   post[j] = p;
  }

  for (j = 0; j < 10 && frente[j] == -1; j++);
  ;//no hacemos nada unicamente nos desplazamos x el vector hasta q salga del ciclo
  primero = frente[j];
  while (j <= 9) {
   for ( i = j+1; i < 10 && frente[i] == -1; i++);
   ;//no hacemos nada unicamente nos desplazamos x el vector hasta q salga del ciclo
   if (i <= 9){
    p = i;
    nodo[post[j]].sig = frente[i];
   }
   j = i;
  }
  nodo[post[p]].sig = -1;
 }
 for ( i = 0; i < N; i++) {
  V[i] = nodo[primero].inf;
  primero = nodo[primero].sig;
 }
}

Descarga el código desde aquí.