
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;
class node
{
public:
int data;
node *next;
node():data(0),next(0){};
node(int item, node *pnext): data(item),next(pnext){};
};
class LinkedQueue
{
public:
LinkedQueue();
~LinkedQueue();
void push(int& item);
void pop();
int& top();
bool empty();
int size();
private:
node* Header;
node* EndNode;
int count;
};
LinkedQueue::LinkedQueue (){count=0;Header=NULL; EndNode = Header;}
LinkedQueue::~LinkedQueue()
{
node* A;
for(;Header!=NULL;)
{
A=Header->next;
delete Header;
Header=A;
}
}
void LinkedQueue::push(int& item)
{
node *newnode=new node (item, 0);
EndNode->next = newnode;
EndNode = EndNode->next;
count++;
}
void LinkedQueue::pop()
{
node *tmp=Header;
Header=Header->next;
delete tmp;
count--;
}
int& LinkedQueue::top()
{
return Header->data;
}
bool LinkedQueue::empty()
{
return count == 0;
}
int LinkedQueue::size()
{
return count;
}
void distribute( vector<int>& v, LinkedQueue digitQueue[], int power)
{
int i;
for (i = 0; i < v.size(); i++)
digitQueue[(v[i] / power) % 10].push(v[i]);
}
void collect(LinkedQueue digitQueue[], vector<int>& v)
{
int i = 0, digit;
for (digit = 0; digit < 10; digit++)
while (!digitQueue[digit].empty())
{
v[i] = digitQueue[digit].top();
digitQueue[digit].pop();
i++;
}
}
void radixSort(vector<int>& v, int d)
{
int i;
int power = 1;
LinkedQueue digitQueue[10];
for (i=0;i < d;i++)
{
distribute(v, digitQueue, power);
collect(digitQueue, v);
power *= 10;
}
}
void displayVector(const vector<int>& v);
int main()
{
int a[]={8,32,56,128,325,991};
vector<int> intVector(a,a+6);
radixSort(intVector, 3);
displayVector(intVector);
return 0;
}
void displayVector(const vector<int>& v)
{
int i;
for (i=0; i < v.size(); i++)
{
cout << setw(12) << v[i];
if ((i+1) % 6 == 0)
cout << endl;
}
cout << endl;
}I
#include <iomanip>
#include <vector>
using namespace std;
class node
{
public:
int data;
node *next;
node():data(0),next(0){};
node(int item, node *pnext): data(item),next(pnext){};
};
class LinkedQueue
{
public:
LinkedQueue();
~LinkedQueue();
void push(int& item);
void pop();
int& top();
bool empty();
int size();
private:
node* Header;
node* EndNode;
int count;
};
LinkedQueue::LinkedQueue (){count=0;Header=NULL; EndNode = Header;}
LinkedQueue::~LinkedQueue()
{
node* A;
for(;Header!=NULL;)
{
A=Header->next;
delete Header;
Header=A;
}
}
void LinkedQueue::push(int& item)
{
node *newnode=new node (item, 0);
EndNode->next = newnode;
EndNode = EndNode->next;
count++;
}
void LinkedQueue::pop()
{
node *tmp=Header;
Header=Header->next;
delete tmp;
count--;
}
int& LinkedQueue::top()
{
return Header->data;
}
bool LinkedQueue::empty()
{
return count == 0;
}
int LinkedQueue::size()
{
return count;
}
void distribute( vector<int>& v, LinkedQueue digitQueue[], int power)
{
int i;
for (i = 0; i < v.size(); i++)
digitQueue[(v[i] / power) % 10].push(v[i]);
}
void collect(LinkedQueue digitQueue[], vector<int>& v)
{
int i = 0, digit;
for (digit = 0; digit < 10; digit++)
while (!digitQueue[digit].empty())
{
v[i] = digitQueue[digit].top();
digitQueue[digit].pop();
i++;
}
}
void radixSort(vector<int>& v, int d)
{
int i;
int power = 1;
LinkedQueue digitQueue[10];
for (i=0;i < d;i++)
{
distribute(v, digitQueue, power);
collect(digitQueue, v);
power *= 10;
}
}
void displayVector(const vector<int>& v);
int main()
{
int a[]={8,32,56,128,325,991};
vector<int> intVector(a,a+6);
radixSort(intVector, 3);
displayVector(intVector);
return 0;
}
void displayVector(const vector<int>& v)
{
int i;
for (i=0; i < v.size(); i++)
{
cout << setw(12) << v[i];
if ((i+1) % 6 == 0)
cout << endl;
}
cout << endl;
}I