Radix Sort Program in C

In this instructional exercise, you will find out about radix sort program in C.

Radix sorting procedure is perhaps the most seasoned system of sorting.

Let’s expect that we are given a rundown of certain names and requested to sort them sequentially.

We would ordinarily continue by first isolating the names into 26 distinct sets (since there is the aggregate of 26 letters in order) with each set

containing names that start with a similar letter set. In the main set, we will put every one of the names which start with letters in order ‘A’.

In the Second Set, we will put every one of the names that start with ‘B, etc.

After this examination of the main letters in order of the considerable number of names,

each set is additionally partitioned into various sub-sets as indicated by the second letters in order of the names.

This procedure proceeds until the rundown turns out to be totally sorted.

Notwithstanding, the downside of radix sorting method is that we need to monitor loads of sets and its sub-sets all the while.

To back out on this disadvantage, there are two strategies accessible in radix sorting:

Most Significant Digit Radix Sort (MSD)

Least Significant Digit Radix Sort (LSD)

In the least critical digit radix sort, sorting is performed digit by digit beginning from the least noteworthy

digit and consummation at the most huge digit.

The idea of most critical sorting is to isolate every one of the digits with an equivalent incentive into their own

set and afterwards accomplish something very similar with every one of the sets until every one of them is sorted.

Examination of Radix Sort ALgorithm

The quantity of passes p is equivalent to the number of digits in the biggest component and in each pass (emphasis) we have

n activities where n is the all outnumber of components. In this program, we can see that the external circle repeats p times and inward circle emphasizes n times.

Thus, run time unpredictability of radix sort is signified by O(p*n).

On the off chance that the quantity of digits in the biggest component is equivalent to n, at that point, the run time becomes O(n square) which is

the direct outcome imaginable in radix sort. The most ideal situation of radix sort is if the quantity of digits in the biggest component is Log n.

For this situation, the run time becomes O(n log n).

The significant inconvenience of radix sort is the requirement for additional memory for keeping up

Queues and thus it’s anything but a setup sort. It is subsequently a steady sort.

Radix Sort Program in C

#include<stdio.h>
#include<stdlib.h>
 
struct  node
{
	int data ;
	struct node *next;
}*start=NULL;
 
void radix_sorting();
int larger_dig();
int digit(int num, int k);
 
main()
{
	struct node *temp,*q;
	int count,n,num_item;
 
	printf("Enter the Number of Elements to be Inserted into the List : ");
	scanf("%d", &n);
 
	for(count=0;count<n;count++)
	{
		printf("Enter element %d : ",count+1);
		scanf("%d",&num_item);
 
		temp= malloc(sizeof(struct node));
		temp->data=num_item;
		temp->next=NULL;
 
		if(start==NULL) 
			start=temp;
		else
		{
			q=start;
			while(q->next!=NULL)
				q=q->next;
			q->next=temp;
		}
	}
 
	radix_sorting();
	printf("Sorted List is :\n");
	
	q=start;
	while( q !=NULL)
	{
		printf("%d ", q->data);
		q = q->next;
	}
	printf("\n");
 
}
 
void radix_sorting()
{
	int count,k,dig,least_sig,most_sig;
	struct node *p, *rear[10], *front[10];
 
	least_sig=1;
	most_sig=larger_dig(start);
 
	for(k=least_sig; k<=most_sig; k++) 
	{
		for(count=0; count<=9 ; count++)
		{
			rear[count] = NULL;
			front[count] = NULL ;
		}
		
		for( p=start; p!=NULL; p=p->next )
		{
			dig = digit(p->data, k);
		
			if(front[dig] == NULL)			
				front[dig] = p ;
			else
				rear[dig]->next = p;
			rear[dig] = p;
		}
		
		count=0;
		while(front[count] == NULL)
			count++;
		start = front[count];	
		while(count<9) 
		{
			if(rear[count+1]!=NULL)
				rear[count]->next=front[count+1];
			else
				rear[count+1]=rear[count];
			count++;
		}
		rear[9]->next=NULL;
	}
}
 
int larger_dig()
{
	struct node *p=start;
	int large=0,ndigit=0;
 
	while(p != NULL)
	{
		if(p ->data > large)
			large = p->data;
		p = p->next ;
	}
 
	while(large != 0)
	{
		ndigit++;
		large = large/10 ;
	}
	return(ndigit);
}
 
int digit(int num, int k)
{
	int digit, count ;
	for(count=1; count<=k; count++)
	{
		digit = num % 10 ;
		num = num /10 ;
	}
	return(digit);

Output

In the event that you discovered anything off base or have questions in regards to above radix sort program in C at that point remark underneath.