Radix Sort Program In C?

Radix-Sort-Program-c

How To Best Implement Radix Sort Program In C?

This article will introduce you Radix Sort and tell you how to implement Radix Sort program in C. Following pointers will be covered in this article,

  • Radix Sort Algorithm
  • Radix Sort function
  • Count Sort Function

So let us get started then,

In basic words, arranging implies orchestrating the given components in an efficient request. Arranging is done in the greater part of the calculations since it makes search simpler which in the long run makes the calculation effective. In this blog we will comprehend one of the normally utilized soring calculations for example Radix sort.

Radix sort is a non-similar whole number arranging calculation. It does digit by digit arranging beginning from least huge digit(i.e. digit present at the option) to most huge digit(i.e. digit present at the left). Radix sort utilizes considering sort a subroutine to sort.

The lower headed for Comparison based arranging calculation, (for example, Heap sort, Quick Sort, Merge Sort) is Ω(nLogn), and they it can’t be improved past nLogn. In the event that we talk about tallying sort, it is a direct time arranging calculation with O(n+k) time multifaceted nature, where the reach lies between 1 to k. Presently, the issue with tallying sort is, it takes O(n2) when the components territory from 1 to n2.

In this way, to sort a cluster with components that range from 1 to n2 in direct time, we need radix sort. Radix sort sorts the exhibit digit by digit beginning from least huge digit to most critical digit. Radix sort utilizes considering sort a subroutine to sort.

Proceeding onward with this article on Radix Sort Program In C,

Radix Sort Algorithm

Perform the following steps for all the digits starting from the least significant digit present in right, moving towards most significant digit present in left.

Sort the elements using counting sort according to the current digit.
Example:

Original Array:
140, 65, 85, 110, 612, 54, 12, 86

Sorting the least significant digit i.e. at one’s place, gives

140, 110, 612, 12, 54, 65, 85, 86

NOTE: As 612 appears before 12, and the sorting is done only for one’s digit, thus 612 appears before 12 after this iteration.

Sorting by next digit, i.e. at 10s place, gives:

110, 612, 12, 140, 54, 65, 85, 86

Sorting by most significant digit, i.e. present at the 100s place, gives:

012, 054, 065, 085, 086, 110, 140, 612

Moving on with this article on Radix Sort Program In C,

Radix Sort Program In C

First look at Radix sort function

Radix Sort function:

1
2
3
4
5
6
7
8
void radixsort(int array[], int n) {
//Get the largest number to know the maximum number of digits
int m = getMax(array, n);
int dig;
//Counting sort is performed for every digit
for (dig = 1; m / dig > 0; dig *= 10)
countSort(array, n, dig);
}

Moving on with this article on Radix Sort Program In C,

Count Sort Function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void countSort(int array[], int n, int dig) {
int output[n];
int i, count[10] = { 0 };
// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[(array[i] / dig) % 10]++;
// Change count[i] so that count[i] now contains actual
//  position of this digit in output[]
for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i >= 0; i--) {
output[count[(array[i] / dig) % 10] - 1] = array[i];
count[(array[i] / dig) % 10]--;
}
// Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to current digit
for (i = 0; i < n; i++)
array[i] = output[i];
}

Advancing ahead, let’s write a C program to implement Radix sort.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<stdio.h>
//Function to find the Largest Number
int getMax(int array[], int n) {
int max = array[0];
int i;
for (i = 1; i < n; i++) if (array[i] > max)
max = array[i];
return max;
}
//Function for Count sort
void countSort(int array[], int n, int dig) {
int output[n];
int i, count[10] = { 0 };
// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[(array[i] / dig) % 10]++;
// Change count[i] so that count[i] now contains actual
//  position of this digit in output[]
for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i >= 0; i--) {
output[count[(array[i] / dig) % 10] - 1] = array[i];
count[(array[i] / dig) % 10]--;
}
// Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to current digit
for (i = 0; i < n; i++) array[i] = output[i]; } // The main function to that sorts arr[] of size n using Radix Sort void radixsort(int array[], int n) { //Get the largest number to know the maximum number of digits int m = getMax(array, n); int dig; //Counting sort is performed for every digit for (dig = 1; m / dig > 0; dig *= 10)
countSort(array, n, dig);
}
//Function to Print Array
void print(int arr[], int n) {
int i;
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
}
int main() {
int arr[] = { 140, 65, 85, 110, 612, 54, 12, 86 };
int n = sizeof(arr) / sizeof(arr[0]);
radixsort(arr, n);
print(arr, n);
return 0;
}

Output

Output- Radix Sort Program in C- Edureka

Now after executing the above program you would have understood the Radix Sort Program In C.