Skip to content

Instantly share code, notes, and snippets.

@rishkarajgi

rishkarajgi/radix_sort.cpp

Created May 26, 2015 21:54
Show Gist options
  • Save rishkarajgi/fba8cced128d2202495e to your computer and use it in GitHub Desktop.
Save rishkarajgi/fba8cced128d2202495e to your computer and use it in GitHub Desktop.
Download ZIP
My implementation of Radix sort in C++
Raw
radix_sort.cpp
#include<iostream>
using namespace std;
struct node
{
int data ;
node * next ;
};
class list
{
private :
node *head ;
public :
list()
{
head = NULL ;
}
void add(int x)
{
node *t = head;
node * temp = new node();
temp -> data = x ;
if(t==NULL)
{
temp->next = NULL;
head = temp ;
}
else
{
while(t->next !=NULL)
{
t = t->next ;
}
temp->next = t->next ;
t->next = temp ;
}
return ;
}
int remove()
{
node *t = head ;
int a = t->data ;
head = t->next ;
delete t;
return a ;
}
int is_empty()
{
if(head==NULL)
return 1;
else
return 0 ;
}
node * view_head()
{
return head ;
}
void print()
{
node * t = head ;
while(t!=NULL)
{
cout << t->data << " " ;
t = t->next;
}
}
};
int max_digit(list &l)
{
int a , dig=0 ,i ;
node *t = l.view_head() ;
a = t->data ;
while(t!=NULL)
{
if(a < t->data)
a = t->data ;
t= t->next ;
}
while(a>0)
{
a = a/10;
dig++;
}
return dig ;
}
int pow(int a , int b)
{
int ans = 1;
while(b--)
{
ans = ans*a ;
}
return ans ;
}
void radix_sort(list & l , list r[])
{
int i = 1 , j , a , b;
int num = max_digit(l);
while(i<=num)
{
while(!l.is_empty())
{
a = l.remove() ;
b = a%pow(10,i);
b = b/pow(10,i-1);
r[b].add(a);
}
for(j=0;j<10;j++)
{
while(!r[j].is_empty())
{
a = r[j].remove();
l.add(a);
}
}
i++;
}
}
int main()
{
list l , r[10];
int a ;
char ch = 'y' ;
while(ch=='y')
{
cout << "Enter a number : ";
cin >> a ;
l.add(a);
cout << "Enter another number ? : ";
cin >> ch ;
}
cout << "List is : " ; l.print();
radix_sort(l , r );
cout << "\nSorted list is : " ; l.print();
return 0 ;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment