In this article I will simulate the Radix sort and also one problem based on the radix sort and solution of that problem.Radix sort is simple sorting algorithm, which running time is linear. Radix sort is also known as the non-comparative sorting of integers algorithm. Radix sort is best for smaller integer numbers because of the in radix sort sorting is done in each digits of numbers. Radix sort start sorting in least significant digits and sort the most significant digits. Time complexity of radix sort is O(n). The working procedure of Radix sort you see with animation
Radix Sort Animation
Problem based on Radix sort and solution is as following:-
Problem:- Design an O(n)-time algorithm that, given a real number x and a array S of n numbers, At first sort it in O(n) time and determines whether or not there exist two elements in S whose sum is exactly x. Solution:- The solution of this problem is Radix sort and then determine whether or not there exist two elements in sorted array whose sum is exactly given real number.
#include <conio.h> #include<stdio.h> #define sz 100 void main() { int a[sz],b[sz],c[sz][sz],p,q,i,j,n,pos,x,sum=0; printf("enter the no of elements "); scanf("%d",&n);printf("enter the element of array"); for(i=1;i<=n;i++) { scanf("%d",&a[i]); p=a[i]/10; q=a[i]%10; c[p][q]=a[i]; } printf("the sorted array is: n"); for(p=0;p<10;p++) { for(q=0;q<10;q++) { for(i=1;i<=n;i++) { if(c[p][q]==a[i]) printf("t %d",a[i]); } } } printf("n enter the real no."); scanf("%d",&x); pos=n; for(i=1;i<=n;i++) { if(x<=a[i]) pos=i; } for(i=1;i<pos;i++) { for(j=i 1;j<=pos;j++) { sum=a[i] a[j]; if(sum==x) printf("n pair are :%d %d",a[i],a[j]); } } getch(); }
Source Code:RADIX.zip
Output:
Output of radix sort with solution of problem |