//Fuente en C: http://es.wikipedia.org/wiki/Ordenamiento_Radix
//Modificado a C++ : sAfOrAs
#include<iostream>
using namespace std;
#include <math.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;
cout<<"Cadena de números enteros:\n";
for (n = 0;; n++)
{
cin>>x[n];
if(x[n]==-1)
break;
}
if (n)
radixsort (x, n);
for (i = 0; i < n; i++)
cout<<x[i]<<endl;;
return 0;
}
Me gusta esto:
Me gusta Cargando...
Relacionado
Para los que dicen que le sale un erro, es porque al código le falta algunas librerías.
#include
#include
#include
#include
#include
#define NUMELTS 20
Estas son todas las librerías que se usa en el código.
#include
puedes hacer un ejemplo con Radix
da error al intentar compilarlo:
radix.cpp: In function ‘int main()’:
radix.cpp:93:22: warning: converting to non-pointer type ‘int’ from NULL [-Wconversion-null]
int x[50] = {NULL}, i;
^
me sale error en el using namespace std;