{"id":11500,"date":"2022-12-29T05:14:36","date_gmt":"2022-12-29T05:14:36","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=11500"},"modified":"2023-06-08T12:54:19","modified_gmt":"2023-06-08T12:54:19","slug":"radix-sort-program-in-c","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/radix-sort-program-in-c\/","title":{"rendered":"Radix Sort Program in C"},"content":{"rendered":"

\"\"<\/p>\n

In this article, we will learn what is radix sort program in C, its algorithm, how it operates with a dry-run example, and how to implement a radix sort program in C with an example.<\/p>\n

What is radix sort?<\/h2>\n

Radix sort is a linear sorting method that is exclusively used to sort arrays of the integer data type. The array is sorted in this algorithm digit by digit. The least significant digit to the most significant digit is sorted. Let’s use an example to illustrate which digit is the least important and which is the most important.<\/p>\n

\"\"<\/p>\n

From the above picture, we will do a sorting from the last significant digit 4 to the most significant digit 7. Thus, in the first pass, we will sort all the elements of the array by the least significant array. After that, we will move toward the most significant digit, digit by digit, and sort the array. Now, let\u2019s see the algorithm of the radix sort.<\/p>\n

Algorithm of the Radix sort:<\/h2>\n

Below is the algorithm for the Radix sort.<\/p>\n

radix_sort(arr)  \nmax_element = largest element in the given array  \ndigits = number of digits in max_element  \nCreate total digit buckets of size 0 - 9  \nfor i -> 0 to digits  \nsort the array elements using counting sort (or any stable sort) according to the digits at the ith place  \n\nmain()\n    radix_sort(arr)<\/code><\/pre>\n
Working of the Radix sort with dry-run:<\/h2>\n
Let\u2019s see how the Radix sort algorithm works using an example. First, we will see some steps to perform the Radix sort algorithm.<\/p>\n
    \n
  • Find the maximum element in the array and store it in max_element.<\/li>\n
  • Calculate the total digits in that max_element and store it in digits.<\/li>\n
  • Now we need to run through all the digits of max_elemnt.<\/li>\n
  • We will go through each digit from the least significant digit to the most significant digit and sort it.<\/li>\n<\/ul>\n
    Now, let\u2019s see how the Radix sort algorithm works. We will take an example and do a dry run as well to understand the working of an algorithm.<\/p>\n
    \"\"<\/p>\n
    We have taken an array of random integers. First, we will find the maximum element in the array which is 954. The maximum element 954 has 3 digits thus the loop will run 3 times and we have to go through 3 passes to sort an array. We will start from the least significant digit ( digit at place 0) to the most significant digit ( digit at place 2).<\/p>\n
    First Pass:<\/strong>
    \nIn the first pass, we will sort an array based on the least significant digit ( digit at 0th place).<\/p>\n
    \"\"<\/p>\n
    In the above picture, we can see that we have stored elements in another array of size 10 based on the least significant digit. After that, we will again transfer all the elements to the original array. Now, our array will look like this:<\/p>\n
    \"\"<\/p>\n
    We will consider the above array for the second pass.<\/p>\n
    Second Pass:<\/strong>
    \nIn the second pass, we will sort an array based on the second least significant digit ( digit at 1st place ).<\/p>\n
    \"\"<\/p>\n
    In the above picture, we can see that we have stored elements in another array based on the second least significant digit ( digit at 1st place ). After that, we will again transfer all the elements to the original array. Now, our array will look like this:<\/p>\n
    \"\"<\/p>\n
    We will consider the above array for the third pass.<\/p>\n
    Third Pass:<\/strong>
    \nIn the second pass, we will sort an array based on the most significant digit ( digit at 2nd place ).<\/p>\n
    \"\"<\/p>\n
    In the above picture, we can see that we have stored elements in another array based on the most significant digit ( digit at 2nd place ). After that, we will again transfer all the elements to the original array. Now, our array will look like this:<\/p>\n
    \"\"<\/p>\n
    After the completion of the third pass, we can see that now our array is sorted.<\/p>\n
    C Program Code of Radix Sort<\/h2>\n
    Now, we have a pretty good idea about how the radix sort algorithm works. Let\u2019s see how to write the radix sort program in c. We will use the counting sort method to implement the radix sort program in c. Counting sort means we will count the numbers having the same digit as the given position and we will store it accordingly. Now, we will write the radix sort program in c. <\/p>\n\t\t\t\t\t\t