Radix Sort
¿Cómo funciona?
Usado en los ordenadores de cartas, se basa en los dígitos como claves.Generalmente conocido como “radix sorting”, “digital sorting”, o “pocket sorting”.
Supongamos que queremos ordenar un mazo de 52 cartas de pocker. Debemos definir:
A < 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < J < Q < K,
como el orden ascendente de los valores de las caras, y para los palos definimos:
(C)lubs < (D)iamons < (H)earts < (S)pades
Una carta precede a otra, si se cumple cualquiera de las dos condiciones:
- su palo es menor que el palo de la otra, o
- los palos son iguales, pero el valor de su cara es menor.
Nota: Este es un caso particular de ordenamiento lexicografico entre pares ordenados de objetos.
Es decir,
A C < 2 C < … < K C < A D < … < Q S < K S.
Es natural ordenar las cartas primero por sus palos en cuatro pilas, luego seguir con cada una de las pilas hasta que estén en orden.
Pero hay una manera más rápida de realizar el truco!
- Distribuir las cartas, con las caras hacia arriba, en 13 pilas, una para cada valor.
- Luego juntamos las pilas poniendo los aces hasta el fondo, los 2s (viendo hacia arriba) encima de ellos, seguimos con los 3s, etc., finalmente ponemos los reyes en la cima.
- Volteamos el mazo completo y repartimos otra vez, esta vez en cuatro pilas para los cuatro palos. Poniendo las pilas resultantes juntas, con los tréboles (Clubs) al fondo, luego los diamantes (Diamons), corazones (Hearts), y espadas (Spade), el mazo estará en perfecto orden.
#
Ejemplo de la ejecución del Radix Sorting sobre un arreglo de enteros
Implementación en C++ usando como algoritmo de ordenamiento estable un quicksort modificado 
!!
(muestra la modificación del arreglo paso a paso)
#include <cstring>
#include <cstdlib>
#define MAX 1002
#define DIGITS 11
//#define DEBUG 1
using namespace std;
char v[MAX][DIGITS];
int partition(char A[][DIGITS],int p,int r, int &index){
char equis[DIGITS],tmp[DIGITS];
sprintf(equis,A[r]);
int i,j;
char x = A[r][index];
int num_x,num;
sscanf (equis,"%d",&num_x);
i= p-1;
for (j=p; j<r; j++){
if (v[j][index] < x){
i++;
strcpy(tmp,A[j]);
strcpy(A[j],A[i]);if two numbers in some digit are the same, you should output the smaller one first
strcpy(A[i],tmp);
}else if(v[j][index]==x){
sscanf (v[j],"%d",&num);
if (num < num_x){
i++;
strcpy(tmp,A[j]);
strcpy(A[j],A[i]);
strcpy(A[i],tmp);
}
}
}
strcpy(tmp,A[i+1]);
strcpy(A[i+1],A[r]);
strcpy(A[r],tmp);
return i+1;
}
void quicksort(char v[][DIGITS],int p,int r, int &index){
int q;
if (p < r){
q = partition(v,p,r,index);
quicksort(v,p,q-1,index);
quicksort(v,q+1,r,index);
}
}
bool cmp(char a,char b){ return a < b; }
void radix_sort(char v[][DIGITS],int a, int b, int n){
int i,k,j;
for (j=b; j>=a; j--){
//insertion_sort(v,n,j);
quicksort(v,0,n-1,j);
//show array
for (i=0; i<n; i++){
// for (k=a; k<=b; k++)
k=a;
while (k<b && v[i][k]=='0')k++;
for(;k<=b; k++)
printf ("%c",v[i][k]);
if (i+1<n) printf (" ");
else printf ("\n");
}
}
}
main(){
int n,num,i,j,index,max_len,len;
char cad[DIGITS];
int casos = 1;
while(scanf ("%d\n",&n) && n){
memset( v, '0', sizeof(v) );
max_len = -1;
for (i=0; i<n; i++){
scanf ("%d",&num);
sprintf(cad,"%d",num);
len = strlen(cad)-1;
if (len > max_len)
max_len = len;
index = DIGITS-2;
for (j=len; j>=0; j--)
v[i][index--] = cad[j];
v[i][DIGITS-1]='\0';
}
printf ("Case %d:\n",casos++);
radix_sort(v,DIGITS-2-max_len,DIGITS-2,n);
#ifdef DEBUG
for(i=0; i<n; i++){
for(j=DIGITS-2-max_len; j<DIGITS-1; j++)
printf ("%c",v[i][j]);
printf ("\n");
}
#endif
}
}
