Privacy Policy

We never collect or share any information of this app user.

This C program demonstrates how RadixSort sorts the given elements by placing them into diff buckets

#include<stdlib.h>
#include<stdio.h>
struct bucket{
	int val;
	struct bucket* next;
};
struct bucket* buckets[10]={NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL};
void print(){
	int i;
	printf("\n-----------------------------------------------------------\n");
	for(i=0;i<10;i++){
		struct bucket*temp=buckets[i];
		printf("\n a[%d] = ",i);
		while(temp){
			printf("%d\t",temp->val);
			temp=temp->next;
		}
	}
}

int digitAt(int n,int p){
	int r;
	while(p>=1){
		r=n%10;
		n=n/10;
		p--;
	}
	return r;
}
int bucketsNotEmpty(){ //except bucket 0
	int i; for(i=1;i<10;i++) if(buckets[i] != NULL) return 1;
	return 0;
}
void addToBucket(int bkt,int ele){
	struct bucket *begin=buckets[bkt];
	struct bucket *temp = (struct bucket *)malloc(sizeof(struct bucket));
	temp->next=NULL;
	temp->val=ele;
	if(buckets[bkt] == NULL){
		buckets[bkt]=temp; return;
	}
	while(begin->next != NULL) begin=begin->next;
	begin->next=temp;
	return;
}
void pushToBuckets(int *a,int n){
	int i,digit;
	for(i=0;i<10;i++){
		digit=digitAt(a[i],1);
		addToBucket(digit,a[i]);
	}
	print();
}
void removeFromBucket(int bkt,int val){
	struct bucket *temp1;
	struct bucket *temp=buckets[bkt];
	if(temp == NULL) return;
	if(temp->val == val){
		buckets[bkt]=temp->next;
		free(temp); return;
	}else{
		while(temp->next->val != val && temp!=NULL) temp=temp->next;
		if(temp == NULL) return;
		temp1=temp->next;
		temp->next=temp->next->next;
		free(temp1);return;
	}
}
void moveElements(int digit){
	int i,val,p; struct bucket *temp;
	for(i=0;i<10;i++){
		temp=buckets[i];
		while(temp){
			val=temp->val;
			p=digitAt(val,digit);
			if( p == i ){
				//do nothing
			}else{
				addToBucket(p,val);
				removeFromBucket(i,val);
				temp=buckets[i]; continue;
			}
			temp=temp->next;
		}
	}
	print();
}
void radixSort(int *a,int n){
	int digit=2;
	pushToBuckets(a,n);
	while(bucketsNotEmpty())
		moveElements(digit++);

}
int main(){
	int i,a[10]={13,45,33,65,3,5,12,4,6,745};
	radixSort(a,10);
	return 0;
}