In this tutorial you will learn about the C Program to implement Radix sort Algorithm and its application with practical example.
C Program to implement Radix sort Algorithm
In this tutorial, we will learn to create a C program that will do Radix sort using C programming.
Prerequisites
Before starting with this tutorial we assume that you are best aware of the following C programming topics:
- Operators in C Programming.
- Basic Input and Output function in C Programming.
- Basic C programming.
- For loop in C Programming.
- Creating and Using the user-defined function in C programming.
What is Radix sort?
In every programming language, the sorting of data is a very important factor. Sorting works are done mainly with the techniques available in C Language. Many different techniques for sorting are available to work with but in this tutorial, we will focus on the Radix Sort Technique.
The Radix Sort is a simple and easy technique. It first makes the group of similar values from a big given array then those small groups are again re-arranged and placed at the deserving positions.
Program for Radix sort
|
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include <stdio.h> int getMaximum(int arr[], int no) { int max = arr[0]; for(int i = 1; i<no; i++) { if(arr[i] > max) max = arr[i]; } return max; //Getting maximum element from the array } void countingSort(int arr[], int no, int place) // function for implement counting sort to program { int output[no + 1]; int count[10] = {0}; // Calculating count of elements for (int i = 0; i < no; i++) count[(arr[i] / place) % 10]++; // Calculating cumulative frequency for (int i = 1; i < 10; i++) count[i] += count[i - 1]; // Placing the elements of array in sorted order/format for (int i = no - 1; i >= 0; i--) { output[count[(arr[i] / place) % 10] - 1] = arr[i]; count[(arr[i] / place) % 10]--; } for (int i = 0; i < no; i++) arr[i] = output[i]; } // function for implement radix sort void radixsort(int arr[], int no) { // maximum element from array grabing int max = getMaximum(arr, no); // Applying counting sort to sort elements based on place value for (int place = 1; max / place > 0; place *= 10) countingSort(arr, no, place); } // function for printing array elements void printArray(int arr[], int no) { for (int i = 0; i < no; ++i) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {971, 328, 358, 827, 869, 139, 595}; int no = sizeof(arr) / sizeof(arr[0]); printf("Before sorting the elements of array are - \n"); printArray(arr,no); radixsort(arr, no); printf("After applying Radix sort,the elements of array are - \n"); printArray(arr, no); } |
Output:-
In the above program we have first initialized the required variable and passed them to other functions for the Radix sort
- no = it will hold the size of the array.
- arr[]= it will hold the elements in an array.
- i= it will hold the integer value to control the array.
- j= it will hold the integer value to control the array.
Now the program will call the print function to display the elements.
After this, the program executes the next function & finds the largest number from the elements of the array.
Now the function to do count sort first
Now, the final step radix function to process the data.
As a result we got the sorted array.
By calling the print function.
