Radix Sort in C++

Radix Sort in C++ is the stable form of counting Sort algorithm used to sort arrays values having same radix and width.

If you don’t know what is counting sort then check counting sort in C++ first.

Some main points about radix sort:

  • Radix sort cannot be applied to all types of data. It can only be used with strings and positive integers (Not with Decimal numbers).
  • Strings and Integers must have same width. Ex [22, 54, 69, 85, 45], [8596, 1025, 7456, 1298, 5200] etc. Notice that every element in the respective array has same length/digits/width.
  • Sorting starts from the rightmost position.
  • Radix sort must use the stable sorting algorithm.

Radix Sort Algorithm

Radix sort algorithm

  1. Sort array elements on the basis of the digits on the 1’s position.
  2. Then, sort the same array elements on the basis of digits on the 10’s position.
  3. Again, sort the array elements on the basis of digits on the 100’s position.
  4. Repeat the process until you are done sorting with Most significant digits. (In our case 100’s position is the most significant digits).
  5. Finally, the array will be sorted.

Note: The above sorting process should be stable i.e the integers having the same digits should not change position relatively.

Radix Sort in C++ Code

get_digit(int a, int p) function is returning the digit at “p” position of “a” integer.

init_with_zero(int arr[]) is initializing  all elements of arr[] to 0. We are using this function for counting_array[] to initialize all its element to zero. So that we can use counting array to count the number of occurence of next significant digit and sort array the original array accordingly.

cal_width(int v) is returning the width of the arr[0], which in our case is 3. This tells us how many times we need to sort the array? i.e number of significant digits.

Output

Radix Sort Overview

  • In-place algorithm.
  • Stable Algorithm (No interchange of integers having duplicates digits).
  • O(n)-complexity.

Also check:

Quick Sort in C++.

Insertion Sort in C.

Shell sort in C++.

admin

I am a B.tech IT Student from India. Technology and programming is the most enthusiastic thing for me in this world. I like learning new techniques and use them for real-world application because I feel tech is future. Let's learn and grow TOGETHER.