Computer Scientists are Pretty Pessimistic

Friday 17 June 2016

Radix Sort

CODE ::

#include <iostream>
#include <cstdlib>
#include <climits>
#include <queue>
using namespace std;
struct node {
    int data;
    struct node *link;
}*head;
void radixSort(int m, node *head)
{
    queue<int>qq[10];
    int i=0,temp;
    while(m>0)
    {
        node *ptr = head->link;
        while(ptr!=NULL)
        {
            temp = ptr->data;
            for(int j=0;j<i;j++)
                temp=temp/10;
            int ind = temp%10;
            qq[ind].push(ptr->data);
            ptr=ptr->link;
        }
        i++;
        m=m/10;
        ptr = head->link;
        for(int i=0;i<10;i++)
        {
            while(!qq[i].empty())
            {
                ptr->data = qq[i].front();
                qq[i].pop();
                ptr = ptr->link;
            }
        }
    }
}
int main()
{
    head = (node*) malloc(sizeof(node));
    head->link = NULL;
    node *temp = head;
    cout<<"Enter Number of elements: "<<endl;
    int n,max=INT_MIN;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        node *newnode = (node*) malloc(sizeof(node));
        newnode->data = rand()%1000;
        newnode->link =temp->link;
        temp->link = newnode;
        temp = newnode;
        max = max > newnode->data ? max : newnode->data;
    }
    radixSort(max,head);
    temp = head->link;
    while(temp!=NULL)
    {
        cout<<temp->data<<" ";
        temp=temp->link;
    }
    return 0;

}

No comments:

Post a Comment