Radix Sort Algorithm #10 by Farrukh Asif

What is Radix Sort?

What Algorithm does it follow? 

Radix Sort Algorithm

The sorting technique known as "radix sort" groups the individual digits of the same place value first. Next, arrange the components in ascending or descending order.
Let's say we have eight elements in our array. Initially, we will arrange the components according to the unit place value. The items will then be sorted according to the value of tenth place. This process continues till the final important location.
Let [121, 432, 564, 23, 1, 45, 788] be the starting array. The graphic below illustrates how it is sorted using radix sort. 

Please go through the counting sort before reading this article because counting sort is used as an intermediate sort in radix sort.

Working of Radix Sort:

1. Determine the array's largest element, or max. Let X be the maximum number of digits. We must go over all of the important locations of every element, so X is calculated.

The greatest number in this array [121, 432, 564, 23, 1, 45, 788] is 788. It has three numbers. As a result, the loop should repeat three times to reach the hundreds place.
2. Next, go over each important location individually.

Sort the numbers at each important location using any reliable sorting method. For this, we've used counting sort.

Sort the elements based on the unit place digits (X=0).

Using counting sort to sort elements based on unit place

1.     Now, sort the elements based on digits at tens place.

       

      Sort elements based on tens place

2.     Finally, sort the elements based on the digits at hundreds place.

3.     Sort elements based on hundreds place

Radix Sort Algorithm:

4.     radixSort(array)

5.       d <- maximum number of digits in the largest element

6.       create d buckets of size 0-9

7.       for i <- 0 to d

8.         sort the elements according to ith place digits using countingSort

9.     countingSort(array, d)

10.  max <- find largest element among dth place elements

11.  initialize count array with all zeros

12.  for j <- 0 to size

13.    find the total count of each unique digit in dth place of elements and

14.    store the count at jth index in count array

15.  for i <- 1 to max

16.    find the cumulative sum and store it in count array itself

17.  for j <- size down to 1

18.    restore the elements to array

19.    decrease count of each element restored by 1

Coding in C language:

// Radix Sort in C Programming

#include <stdio.h>

// Function to get the maximum value in the array

int getMax(int array[], int n) {

int max = array[0];

for (int i = 1; i < n; i++) {

if (array[i] > max) {

max = array[i];

}

}

return max;

}

// Using counting sort to sort the elements based on significant places

void countingSort(int array[], int n, int place) {

int output[n];

int count[10] = {0};

// Calculate count of elements

for (int i = 0; i < n; i++) {

int index = (array[i] / place) % 10;

count[index]++;

}

// Calculate cumulative count

for (int i = 1; i < 10; i++) {

count[i] += count[i - 1];

}

// Place the elements in sorted order

for (int i = n - 1; i >= 0; i--) {

int index = (array[i] / place) % 10;

output[count[index] - 1] = array[i];

count[index]--;

}

// Copy the sorted elements into original array

for (int i = 0; i < n; i++) {

array[i] = output[i];

}

}

// Main function to implement radix sort

void radixSort(int array[], int n) {

// Get maximum element

int maxElement = getMax(array, n);

// Apply counting sort to sort elements based on place value

for (int place = 1; maxElement / place > 0; place *= 10) {

countingSort(array, n, place);

}

}

int main() {

int data[] = {121, 432, 564, 23, 1, 45, 788};

int n = sizeof(data) / sizeof(data[0]);

radixSort(data, n);

printf("Sorted array in ascending order:\n");

for (int i = 0; i < n; i++) {

printf("%d ", data[i]);

}

return 0;

}

 

Radix Sort Applications

Radix sort is implemented in

• DC3 algorithm while making a suffix array.
• places where there are numbers in large ranges.

 

============================

 Like, Share and Comments Please....

============================