Our Feeds

Friday 4 December 2015

AJITH KP

Implementation of Radix Sort in C++

Hi guyz,
     According to Wikipedia[^] radix sort is described as,
``In computer science, radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. A positional notation is required, but because integers can represent strings of characters (e.g., names or dates) and specially formatted floating point numbers, radix sort is not limited to integers. Radix sort dates back as far as 1887 to the work of Herman Hollerith on tabulating machines.```.



     The implementation of radix sort in c++

#include <iostream>
#include <queue>
/*
 * 
 * Coded By Ajith Kp [@ajithkp560]
 * http://www.terminalcoders.blogspot.com
 * 
 */
using namespace std;
int main(){
 int n, flg, i, nw, d, t;
 cout<<"Enter limit: ";
 cin>>n;
 int *arr = new int[n];
 cout<<"Enter "<<n<<" items: ";
 for(i=0;i<n;i++){
  cin>>arr[i];
 }
 flg = 0;
 d = 1;
 while(!flg){
  flg = 1;
  queue<int> Q[10];
  for(i=0;i<n;i++){
   nw = (arr[i]/d);
   if(nw>0){
    flg = 0;
   }
   Q[nw%10].push(arr[i]);
  }
  t = 0;
  for(i=0;i<10;i++){
   while(!Q[i].empty()){
    arr[t++] = Q[i].front();
    Q[i].pop();
   }
  }
  d = d*10;
 }
 cout<<"Sorted List: ";
 for(i=0;i<n;i++)cout<<arr[i]<<" ";cout<<endl;
}