Radix sort
Radix sort is a sorting algorithm that is used to arrange the elements of an
array in a particular sorted order.
In radix sort, there is digit by digit sorting is performed that is started from
the least significant digit to the most significant digit.
It is a digit-by-digit sorting algorithm which makes it faster than most
sorting algorithms including merge sort and quick sort as well.
Radix sort program in C sorts the array in linear time but the data must be
between ranges of elements.
RADIX SORT ALGORITHM
a) radixsort(A,n)//a=array_element,n=no of element
{
int max=getmax(A,n)//get the largest element using function getmax()
For (pos=1, max/pos>0; pos*10)
{
Countsort(A,n,pos);
}
}
// sort the elements digits according to position digits using countingSort()
b) Countsort(int A,int n,int pos)
{
Int count[10]={0};
For(i=0;i<n;i++)
count[(A[i] / pos) % 10]++;
For(i=1;i<=n;i++)
count[i]= count[i] + count[i - 1];
For(i=n-1;i>=0;i--)
b[--count[(A[i] / pos) % 10] ] = A[i];
For(i=0;i<=n;i++)
A[i]=b[i];
}
Problem Solution
Example: (Working of radix sort)
Let’s say we have this array, containing 10 elements. Name of this array is arr.
arr [10] = {530,090,231,011,432,045,677,008,088,199}
1st Iteration:pass1:
According to the numbers at the least significant bit position
are 0,0,1,1,2,5,7,8,8,9
We will arrange them from lowest to highest using count sort.
0 1 2 3 4 5 6 7 8 9
count 2 2 1 0 0 1 0 1 2 1
Count[i] 2 4 5 5 5 6 6 7 9 10
1st 1 3 4 5 6 8 9
decrement
2nd 0 2 7
decrement
B[i] 530 090 231 011 432 045 677 008 088 199
2nd iteration:pass2:
after the pass 1,the temporary array value b[i] are
530 090 231 011 432 045 677 008 088 199
Form pass 1 ,According to the numbers at the 2nd least significant bit position
are
We will arrange them from lowest to highest using count sort.
0 1 2 3 4 5 6 7 8 9
count 1 1 0 3 1 0 0 1 1 2
Count[i] 1 2 2 5 6 6 6 7 8 10
1st 0 1 4 5 6 7 9
decrement
2nd 3 8
decrement
B[i] 008 011 530 231 432 045 677 088 090 199
2nd Iteration:pass3:
after the pass 2,the temporary array value b[i] are
008 011 530 231 432 045 677 088 090 199
Form pass 1 ,According to the numbers at the 3rd least significant bit position
are 0,0,5,2,4,0,6,0,0,1
We will arrange them from lowest to highest using count sort.
0 1 2 3 4 5 6 7 8 9
count 5 1 1 0 1 1 1 0 0 0
Count[i] 5 6 7 7 8 9 10 10 10 10
1st 4 5 6 7 8 9
decrement
2nd 3
decrement
3rd 2
decrement
4th 1
decrement
5th 0
decrement
B[i] 008 011 045 088 090 199 231 432 530 677
We have reached the end of the iteration and we have sorted our array as well.
After sorting, we have the following array
008 011 045 088 090 199 231 432 530 677
//c program for radix sort.
#include <stdio.h>
// Function to find the maximum element in the array
int findMax(int array[], int n) {
int max = array[0];
for (int i = 1; i < n; i++) {
if (array[i] > max) {
max = array[i];
}
}
return max;
}
// A function to do counting sort of the elements based on significant place
void countSort(int array[], int size, int place) {
const int max = 10;
int output[size];
int count[max];
for (int i = 0; i < max; ++i)
count[i] = 0;
// Calculate the count of elements
for (int i = 0; i < size; i++)
count[(array[i] / place) % 10]++;
// Calculate the cumulative count
for (int i = 1; i < max; i++)
count[i] += count[i - 1];
// Place the elements in sorted order
for (int i = size - 1; i >= 0; i--) {
output[count[(array[i] / place) % 10] - 1] = array[i];
count[(array[i] / place) % 10]--;
}
//display the element
for (int i = 0; i < size; i++)
array[i] = output[i];
}
// Main function to implement radix sort
void radixsort(int array[], int size)
{
// Find the maximum number to know the number of digits
int max = findMax(array, size);
// Do counting sort for every digit. Note that
// instead of passing the place, exp is passed.
// exp is 10^i where i is the current digit number
for (int place = 1; max / place > 0; place *= 10)
countSort(array, size, place);
}
int main() {
int size;
printf("Enter the number of elements: ");
scanf("%d", &size);
int array[size];
printf("Enter the elements:\n");
for (int i = 0; i < size; i++) {
scanf("%d", &array[i]);
}
radixsort(array, size);
printf("Sorted array: \n");
for (int i = 0; i < size; i++) {
printf("%d ", array[i]);
}
return 0;
}
Output:
Enter the number of elements: 5
Enter the elements:
23
5
211
99
555
Sorted array:
5 23 99 211 555
