Tutorial Playlist

Data Structure Tutorial

Overview

Arrays in Data Structures: A Guide With Examples

Lesson - 1

All You Need to Know About Two-Dimensional Arrays

Lesson - 2

All You Need to Know About a Linked List in a Data Structure

Lesson - 3

The Complete Guide to Implement a Singly Linked List

Lesson - 4

The Ultimate Guide to Implement a Doubly Linked List

Lesson - 5

The Fundamentals for Understanding Circular Linked List

Lesson - 6

The Ultimate Guide To Understand The Differences Between Stack And Queue

Lesson - 7

Implementing Stacks in Data Structures

Lesson - 8

Your One-Stop Solution for Stack Implementation Using Array

Lesson - 9

Your One-Stop Solution for Queue Implementation Using Array

Lesson - 10

Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

Lesson - 11

Your One-Stop Solution for Stack Implementation Using Linked-List

Lesson - 12

The Definitive Guide to Understand Stack vs Heap Memory Allocation

Lesson - 13

All You Need to Know About Linear Search Algorithm

Lesson - 14

All You Need to Know About Breadth-First Search Algorithm

Lesson - 15

A One-Stop Solution for Using Binary Search Trees in Data Structure

Lesson - 16

The Best Tutorial to Understand Trees in Data Structure

Lesson - 17

A Complete Guide to Implement Binary Tree in Data Structure

Lesson - 18

A Holistic Look at Using AVL Trees in Data Structures

Lesson - 19

All You Need to Know About Tree Traversal in Data Structure

Lesson - 20

The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

Lesson - 21

The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

Lesson - 22

The Best and Easiest Way to Understand an Algorithm

Lesson - 23

Your One-Stop Solution to Understand Shell Sort Algorithm

Lesson - 24

Your One-Stop Solution to Quick Sort Algorithm

Lesson - 25

The Most Useful Guide to Learn Selection Sort Algorithm

Lesson - 26

Everything You Need to Know About Radix Sort Algorithm

Lesson - 27

Everything You Need to Know About the Counting Sort Algorithm

Lesson - 28

Everything You Need to Know About the Merge Sort Algorithm

Lesson - 29

Insertion Sort Algorithm: One-Stop Solution That Will Help You Understand Insertion Sort

Lesson - 30

Everything You Need to Know About the Bubble Sort Algorithm

Lesson - 31

The Best Guide You’ll Ever Need to Understand Bucket Sort Algorithm

Lesson - 32

Your One-Stop Solution to Understand Recursive Algorithm in Programming

Lesson - 33

The Definitive Guide to Understanding Greedy Algorithm

Lesson - 34

Your One-Stop Solution to Understand Backtracking Algorithm

Lesson - 35

The Fundamentals of the Bellman-Ford Algorithm

Lesson - 36

Your One-Stop Solution for Graphs in Data Structures

Lesson - 37

The Best Guide to Understand and Implement Solutions for Tower of Hanoi Puzzle

Lesson - 38

A Simplified and Complete Guide to Learn Space and Time Complexity

Lesson - 39

All You Need to Know About the Knapsack Problem : Your Complete Guide

Lesson - 40

The Fibonacci Series: Mathematical and Programming Interpretation

Lesson - 41

The Holistic Look at Longest Common Subsequence Problem

Lesson - 42

The Best Article to Understand What Is Dynamic Programming

Lesson - 43

A Guide to Implement Longest Increasing Subsequence Using Dynamic Programming

Lesson - 44

A Holistic Guide to Learn Stop Solution Using Dynamic Programming

Lesson - 45

One Stop Solution to All the Dynamic Programming Problems

Lesson - 46

Understanding the Fundamentals of Binomial Distribution

Lesson - 47
Everything You Need to Know About Radix Sort Algorithm

Radix sort algorithm is a non-comparative sorting algorithm in computer science. It avoids comparison by creating and categorizing elements based on their radix. For elements with more than one significant digit, it repeats the bucketing process for each digit while preserving the previous step's ordering until all digits have been considered. As a result, radix sort is also known as bucket sort and digital sort.

What Is a Radix Sort Algorithm?

  • Radix Sort is a linear sorting algorithm.
  • Radix Sort's time complexity of O(nd), where n is the size of the array and d is the number of digits in the largest number.
  • It is not an in-place sorting algorithm because it requires extra space.
  • Radix Sort is a stable sort because it maintains the relative order of elements with equal values.
  • Radix sort algorithm may be slower than other sorting algorithms such as merge sort and Quicksort if the operations are inefficient. These operations include sub-inset lists and delete functions, and the process of isolating the desired digits.
  • Because it is based on digits or letters, radix sort is less flexible than other sorts. If the type of data changes, the Radix sort must be rewritten.

what-is-radix-sort-algorithm.

After defining the radix sort algorithm, you will look at how it works with an example.

Post Graduate Program: Full Stack Web Development

in Collaboration with Caltech CTMEEnroll Now
Post Graduate Program: Full Stack Web Development

Working of Radix Sort Algorithm

  • The Radix sort algorithm works by ordering each digit from least significant to most significant. 
  • In base 10, radix sort would sort by the digits in the one's place, then the ten's place, and so on.
  • To sort the values in each digit place, Radix sort employs counting sort as a subroutine.
  • This means that for a three-digit number in base 10, counting sort will be used to sort the 1st, 10th, and 100th places, resulting in a completely sorted list. Here's a rundown of the counting sort algorithm.

Assume you have an 8-element array. First, you will sort the elements by the value of the unit place. It will then sort the elements based on the value of the tenth position. This process is repeated until it reaches the last significant location.

Let's start with [132, 543, 783, 63, 7, 49, 898]. It is sorted using radix sort, as illustrated in the figure below.

  • Find the array's largest element, i.e., maximum. Consider A to be the number of digits in maximum. A is calculated because we must traverse all of the significant locations of all elements.

The largest number in this array [132, 543, 783, 63, 7, 49, 898] is 898. It has three digits. As a result, the loop should be extended to hundreds of places (3 times).

  • Now, go through each significant location one by one. Sort the digits at each significant place with any stable sorting technique. You must use counting sort for this. Sort the elements using the unit place digits (A = 0).

working-of-radix-sort-algorithm

  • Sort the elements now by digits in the tens place.

working-of-radix-sort-algorithm1

  • Finally, sort the elements by digits in the hundreds place.

working-of-radix-sort-algorithm2

In this tutorial, you will look at the pseudocode for the radix sort algorithm.

Pseudocode of Radix Sort Algorithm

Radix_Sort(Array, p) // p is the number of passes

       for j = 1 to p do

            int count_array[10] = {0};

            for i = 0 to n do

                count_array[key of(Array[i]) in pass j]++ // count array stores the count of key

            for k = 1 to 10 do

                count_array[k] = count_array[k] + count_array[k-1]

            for i = n-1 downto 0 do

                result_array[ count_array[key of(Array[i])] ] = Array[j]

                                                          //Construct the resulting array (result_array) by checking

                                                                                 //new Array[i] position from count_array[k]

                count_array[key of(Array[i])]--

            for i=0 to n do

                Array[i] = result_array[i]  

                                                             //The main array Array[] now contains sorted numbers based on the current digit position.

       the end for(j)

 end function

After understanding the pseudocode of the radix sort algorithm, you will now examine its performance in this tutorial.

New Course: Full Stack Development for Beginners

Learn Git Command, Angular, NodeJS, Maven & MoreEnroll Now
New Course: Full Stack Development for Beginners

Performance of Radix Sort Algorithm

The Time Complexity of Radix Sort Algorithm

Worst-Case Time Complexity

In radix sort, the worst case is when all elements have the same number of digits except one, which has a significantly large number of digits. If the number of digits in the largest element equals n, the runtime is O. (n2).

Best Case Time Complexity

When all elements have the same number of digits, the best-case scenario occurs. O(a(n+b)) is the best-case time complexity. If b equals O(n), the time complexity is O. (a*n).

Average Case Time Complexity

You considered the distribution of the number of digits in the average case. There are 'p' passes, and each digit can have up to 'd' different values. Because radix sort is independent of the input sequence, we can keep n constant.

T(n) = p(n+d) is the running time of radix sort. Using the linearity of expectation and taking into account both sides' expectations.

Radix sort has an average case time complexity of O(p*(n+d)).

The Space Complexity of Radix Sort Algorithm

Because Radix sort employs Counting sort, which uses auxiliary arrays of sizes n and k, where n is the number of elements in the input array and k is the largest element among the dth place elements (ones, tens, hundreds, and so on) of the input array. Hence, the Radix sort has a space complexity of (n+k).

Stability of Radix Sort Algorithm

Radix Sort algorithm is a stable sorting subroutine-based integer sorting algorithm. It is a sorting algorithm that does not use comparisons to sort a collection of integers. It classifies keys based on individual digits with the same significant position and value.

Moving forward in this tutorial, you will look at some of its benefits and drawbacks.

Advantages Radix Sort Algorithm

Following are some advantages of the radix sorting algorithm:

  • Fast when the keys are short, i.e. when the array element range is small.
  • Used in suffix arrays construction algorithms such as Manber's and the DC3 algorithm.
  • Radix Sort is a stable sort because it maintains the relative order of elements with equal values.

Disadvantages of Radix Sort Algorithm

Following are some disadvantages of the radix sorting algorithm:

  • The Radix Sort algorithm is less flexible than other sorts because it is based on digits or letters. As a result, for each different type of data, it must be rewritten.
  • Radix sort has a higher constant than other sorting algorithms.
  • It takes up more space than Quicksort, which is used for in-place sorting.
  • Radix sort may be slower than other sorting algorithms such as merge sort and Quicksort if the operations are inefficient. These operations include sub-inset lists and delete functions, as well as the process of isolating the desired digits.
  • Because it is based on digits or letters, the radix sort is less flexible than other sorts. If the data type must be rewritten, so must the Radix sort.

Now that you have explored the benefits and drawbacks of the radix sort algorithm, look at some of its applications.

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
Full Stack Web Developer Course

Applications of Radix Sort Algorithm

These are some applications of radix sort:

  • The Radix sort algorithm is used in a typical computer, a sequential random-access machine, multiple fields key records.
  • While creating a suffix array, use the DC3 algorithm (Kärkkäinen-Sanders-Burkhardt).
  • The Radix sort algorithm locates locations where there are numbers in extensive ranges.

Finally, in this tutorial, you will look at the code implementation of the radix sort algorithm.

Code Implementation of Radix Sort Algorithm

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>                             

int Max_value(int Array[], int n) // This function gives maximum value in array[]

{

    int i;

    int maximum = Array[0];

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

        if (Array[i] > maximum)

            maximum = Array[i];

    }

    return maximum;

}

void radixSortalgorithm(int Array[], int n) // Main Radix Sort sort function

{

    int i,digitPlace = 1;

    int result_array[n]; // resulting array

    int largest = Max_value(Array, n); // Find the largest number to know number of digits

    while(largest/digitPlace >0){

        int count_array[10] = {0};

        for (i = 0; i < n; i++) //Store the count of "keys" or digits in count[]

            count_array[ (Array[i]/digitPlace)%10 ]++;

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

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

        for (i = n - 1; i >= 0; i--) // Build the resulting array

        {

            result_array[count_array[ (Array[i]/digitPlace)%10 ] - 1] = Array[i];

            count_array[ (Array[i]/digitPlace)%10 ]--;

        }

        for (i = 0; i < n; i++) // numbers according to current digit place   

            Array[i] = result_array[i];

            digitPlace *= 10; // Move to next digit place

    }

}

void displayArray(int Array[], int n) // Function to print an array

{

    int i;

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

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

    printf("\n");

}

int main()

{

    int array1[] = {20,30,40,90,60,100,50,70};

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

    printf("Unsorted Array is : ");

    displayArray(array1, n);

    radixSortalgorithm(array1, n);

    printf("Sorted Array is: ");

    displayArray(array1, n);

    return 0;

}

Output

output-of-radix-sort-program-in-C

Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

Next Steps

In this tutorial, you learned about the radix sort algorithm and its working process with an example and some applications of the radix sort algorithm.

If you're searching for a more extensive study that goes beyond Data Structure and covers the most in-demand programming languages and abilities today, then Simplilearn’s Post Graduate Program in Full Stack Web Development is for you. 

Do you have any questions about this tutorial on the radix sort algorithm? If you do, please leave them in the comments section at the bottom of this page. Our specialists will respond to your questions as quickly as possible!

About the Author

SimplilearnSimplilearn

Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.