radix sort 2 Algorithm
radix sort can be apply to data that can be sorted lexicographically, be they integers, words, punch cards, playing cards, or the mail. It avoids comparison by make and distribute components into buckets according to their radix. radix sorting algorithms get into common purpose as a manner to sort punched cards as early as 1923.The first memory-efficient computer algorithm was developed in 1954 at MIT by Harold H. Seward. The linear scan is closely associated to Seward's other algorithm — counting sort. computerize radix kinds had previously been dismissed as impractical because of the perceived need for variable allocation of buckets of unknown size.
//sorting of array list using Radix sort
#include <stdio.h>
#define range 10 // Range for integers is 10 as digits range from 0-9
// Utility function to get the maximum value in ar[]
int MAX(int ar[], int size){
int i, max = ar[0];
for(i = 0; i<size; i++){
if(ar[i]>max)
max = ar[i];
}
return max;
}
// Counting sort according to the digit represented by place
void countSort(int arr[],int n,int place)
{
int i,freq[range]={0};
int output[n];
// Store count of occurences in freq[]
for(i=0;i<n;i++)
freq[(arr[i]/place)%range]++;
// Change freq[i] so that it contains the actual position of the digit in output[]
for(i=1;i<range;i++)
freq[i]+=freq[i-1];
// Build the output array
for(i=n-1;i>=0;i--)
{
output[freq[(arr[i]/place)%range]-1]=arr[i];
freq[(arr[i]/place)%range]--;
}
// Copy the output array to arr[], so it contains numbers according to the current digit
for(i=0;i<n;i++)
arr[i]=output[i];
}
/*This is where the sorting of the array takes place
arr[] --- Array to be sorted
n --- Array Size
max --- Maximum element in Array
*/
void radixsort(int arr[],int n,int max) //max is the maximum element in the array
{
int mul=1;
while(max)
{
countsort(arr,n,mul);
mul*=10;
max/=10;
}
}
int main(int argc, const char * argv[]){
int n;
printf("Enter size of array:\n");
scanf("%d", &n); // E.g. 8
printf("Enter the elements of the array\n");
int i;
int arr[n];
for(i = 0; i < n; i++){
scanf("%d", &arr[i] );
}
printf("Original array: ");
display(arr, n); // Original array : 10 11 9 8 4 7 3 8
int max;
max = MAX(arr,n);
radixsort(arr, n, max);
printf("Sorted array: ");
display(arr, n); // Sorted array : 3 4 7 8 8 9 10 11
return 0;
}
