Radix Sort
#include
using namespace std;
struct Node
{
int data;
Node *next;
};
struct Queue
{
Node *head;
Node *tail;
};
Node* Creat_Node(int x)
{
Node *p = new Node;
if(p == NULL)
{
cout<<"\n\tLoi cap phat bo nho.!";
return NULL;
}
p->data = x;
p->next = NULL;
return p;
}
void Creat_Queue(Queue &q)
{
q.head = q.tail = NULL;
}
bool IsEmpty(Queue q)
{
return (q.head == NULL);
}
void Push(Queue &q, int x)
{
Node *p = Creat_Node(x);
if(q.head == NULL)
{
q.head = q.tail = p;
}
else
{
q.tail->next=p;
q.tail = p;
}
}
void Pop(Queue &q)
{
if(IsEmpty(q))
{
cout<<"\n\tDanh sach rong.!";
return;
}
Node *p = q.head;
q.head = q.head->next;
delete p;
}
int Top(Queue q)
{
if(IsEmpty(q))
{
cout<<"\n\tDanh sach rong.!";
return NULL;
}
return q.head->data;
}
void Print_Queue(Queue q)
{
if(IsEmpty(q))
{
cout<<"\n\tDanh sach rong.!";
}
while(!IsEmpty(q))
{
cout<data<<" ";
q.head = q.head->next;
}
}
void Inp_Arr(int a[], int n)
{
for(int i = 0; i < n ; i++)
{
cout<<"\n\tNhap : ";
cin>>a[i];
}
}
void Print_Arr(int a[], int n)
{
for(int i = 0; i < n; i++)
{
cout<<>
}
}
void Radix_Sort(int a[], int n)
{
Queue q[10];
int max = a[0], h = 1;
for(int i = 0; i < n; i++)
if(max < a[i]) max = a[i];
for(int i = 0; i < 10; i++)
{
Creat_Queue(q[i]);
}
while(max / h > 0)
{
for(int i = 0 ; i < n; i++)
{
int temp = a[i]/h % 10;
Push(q[temp], a[i]);
}
int k = 0;
for(int i = 0; i < 10; i++)
{
while(!IsEmpty(q[i]))
{
a[k++] = q[i].head->data;
q[i].head = q[i].head->next;
}
}
h *= 10;
}
Print_Arr(a, n);
}
int main()
{
int a[10] = {123, 54, 65, 87, 99, 8, 72, 45, 23, 24};
int n = 10;
Radix_Sort(a, n);
system("pause");
return 0;
}