Radix Sort Using Circular Queue
(see also the Java Solution)
#include < fstream.h >
#include < iostream.h >
#include < stdlib.h >
#include < stdio.h >
void intdisplay(void *t) { cout << *(int *)t << " "; }
class Cell
{
friend class Queue;
public:
Cell(void *ptr, Cell *lst)
{
item = ptr;
next = lst;
}
private:
void *item;
Cell *next;
};
class Queue
{
public:
Queue() { dispfn = intdisplay; tail = NULL; }
void enqueue(void *t);
void *dequeue();
void append(Queue *q);
void display();
Cell *trailer() { return tail; }
int empty() { return tail == NULL; }
private:
Cell *tail;
void (* dispfn)(void *);
};
void Queue::enqueue(void *t)
{
Cell *h;
if (t == NULL) return;
if (tail == NULL)
{
tail = new Cell(t, NULL);
tail->next = tail;
}
else
{
h = new Cell(t, tail->next);
tail->next = h;
tail = h;
}
}
void *Queue::dequeue()
{
if (tail == NULL) return NULL;
Cell *ptr = tail->next;
void *t = ptr->item;
if (ptr != tail)
tail->next = ptr->next;
else
tail = NULL;
delete ptr;
return t;
}
void Queue::append(Queue *q)
{
Cell *ptr;
if (tail == NULL) tail = q->trailer();
else
if (!q->empty())
{
ptr = q->trailer()->next;
q->trailer()->next = tail->next;
tail->next = ptr;
tail = q->trailer();
}
}
void Queue::display()
{
Cell *t;
if (tail == NULL) { cout << "(empty)\n"; return; }
for (t=tail->next ; t != tail ; t=t->next) (dispfn)(t->item);
(dispfn)(tail->item);
printf("\n");
}
int GetDigit(int number, int place)
{
int i;
for (i=0; i < place ; i++) number /= 10;
return number % 10;
}
int ReadData(Queue *q, char *filename)
{
char *buffer = new char[128];
int number, count=0;
fstream fin(filename, ios::in);
while (fin.getline(buffer, 128, '\n'))
{
sscanf(buffer, "%d", &number);
q->enqueue((void *)new int(number));
count++;
}
fin.close();
return count;
}
void main(int argc, char **argv)
{
Queue *q = new Queue();
Queue *p[10];
int *numb, count=0, i, j;
if (argc != 3)
{
printf("\nUsage: RADIX < filename > < max no. digits in numbers >\n");
printf("File format: one line for each integer");
exit(0);
}
count = ReadData(q, argv[1]);
for (j=0 ; j < atoi(argv[2]) ; j++)
{
for (i=0 ; i < 10 ; i++) p[i] = new Queue();
for (i=0 ; i < count ; i++)
{
numb = (int *)q->dequeue();
p[GetDigit(*numb,j)]->enqueue(numb);
}
for (i=0 ; i < 10 ; i++)
{
q->append(p[i]);
delete p[i];
}
}
q->display();
}