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í.
