Radix Sort Algorithm

Definition of Radix Sort Algorithm

Radix sort algorithm is a sorting algorithm to sort a list of numbers using smaller numbers. The radix sort algorithm is a non-comparison algorithm for sorting a group of digits without comparison digits with each other. The radix sort algorithm is an algorithm uses in java, python, PHP, C++ language to sort array numbers. The radix sort algorithm is a sort input array numbers based on the least significant number and sort number one by one. The radix sort is similar to a bucket list to overcome the drawback of the sorting algorithm and sorts multiple numbers without comparison. The number of radix or base specifies the position of the single-digit and sorts the multiple numbers is a called as a radix sort algorithm. The radix sort is counting sort of the list of a number from least significant value to most significant value.

Radix Sort Algorithm

The radix sort is based on least digit to most digits. This digit sorts based on the place of the number. The radix sort algorithm steps are below.

Step 1: Set up the number of the array and find the position of the numbers.

Step 2: Set up several positions and several digits. Set a maximum number of the array list.

Step 3: Set SORT = 0 positions.

Step 4: Go to the first digit of the numbers.

Step 5: Find the least significant to the most significant digit.

Step 6: Change the position of the array number as per number.

Step 7: the bucket count of the digit and position one by one.

Step 8: Repeat the fourth step until the last position fulfills the condition.

Step 9: Repeat the sixth step until the position of the digits fulfills the condition.

Step 10: End the loop of the sorting array numbers.

Step 11: End the procedure of the radix sort algorithm.

Working procedure of the Radix sort algorithm

The number of the list contains in the array form. The given array is shown below.

Array = {943, 36, 4, 2015, 300, 452}

The number sort with 0’s digit of the position.

Array = {300, 452, 943, 4, 2015, 36}

The number sort with 10’s digit of the position.

Array = {300, 04, 2015, 36, 943, 452}

The number sort with 100’s digit of the position.

Array = {04, 2015, 36, 300, 452, 943}

The number sort with 1000’s digit of the position.

Array = {04, 36, 300, 452, 943, 2015}

Advantages and Disadvantages

Advantages of the radix sort algorithm

1. The radix sort performs better and faster than the quick sort.
2. The radix sort is a stable sort to classify the numbers.
3. The radix sorts maintain equal values.
4. The radix sort is provided an easy and simple algorithm.
5. This algorithm does not work in comparison operation with a list of numbers.

Disadvantages of the radix sort algorithm

1. The radix sort contains a large space for sorting the numbers.
2. The radix sort does not apply to all data types’ values. You apply only integral values.
3. The radix sort algorithm does not provide better efficiency.
4. This algorithm does not use for tightly clustered values.

Examples

Let us discuss examples of Radix Sort Algorithm.

Example #1: the radix sort algorithm using java language example and output is below.

import java.io.*;
import java.util.*;
public class Radixsortalgorithm {
static int getMax(int array_sory[], int arr_lenth)
{
int max_num = array_sory[0];
for (int a = 1; a < arr_lenth; a ++)
if (array_sory[a] > max_num)
max_num = array_sory[a];
return max_num;
}
public static void main(String[] args)
{
int array_sory[] = { 10,1045, 765, 91, 02, 524, 66, 27 };
int arr_lenth = array_sory.length;
radixSortalgorithm(array_sory, arr_lenth);
display(array_sory, arr_lenth);
}
static void numberSort(int array_sory[], int arr_lenth, int e)
{
int output[] = new int[arr_lenth];
int a;
int count[] = new int[10];
Arrays.fill(count, 0);
for (a = 0; a < arr_lenth; a++)
count[(array_sory[a] / e) % 10]++;
for (a = 1; a < 10; a ++)
count[a] += count[a - 1];
for (a = arr_lenth - 1; a >= 0; a --) {
output[count[(array_sory[a] / e) % 10] - 1] = array_sory[a];
count[(array_sory[a] / e) % 10]--;
}
for (a = 0; a < arr_lenth; a++)
array_sory[a] = output[a];
}
public static void radixSortalgorithm(int array_sory[], int arr_lenth)
{
int mg = getMax(array_sory, arr_lenth);
for (int e = 1; mg / e > 0; e*= 10)
numberSort(array_sory, arr_lenth, e);
}
public static void display(int array_sory[], int arr_lenth)
{
for (int a = 0; a < arr_lenth; a++)
System.out.print(array_sory[a] + " ");
}
}

Output:

Example #2: The radix sort algorithm using PHP language example and output is below.

<?php
function numberSort(&$arr_number, $length, $e)
{
$output_number = array_fill(0, $length, 0);
$count_number = array_fill(0, 10, 0);
for ($a = 0; $a < $length; $a++)
$count_number[ ($arr_number[$a] / $e) % 10 ]++;
for ($a = 1; $a < 10; $a++)
$count_number[$a] += $count_number[$a - 1];
for ($a = $length - 1; $a >= 0; $a--)
{
$output_number[$count_number[ ($arr_number[$a] /
$e) % 10 ] - 1] = $arr_number[$a];
$count_number[ ($arr_number[$a] / $e) % 10 ]--;
}
for ($a = 0; $a < $length; $a++)
$arr_number[$a] = $output_number[$a];
}
function radixsortalgorithm(&$arr_number, $length)
{
$m = max($arr_number);
for ($e = 1; $m / $e > 0; $e *= 10)
numberSort($arr_number, $length, $e);
}
function PrintSortedArray(&$arr_number,$length)
{
for ($a = 0; $a < $length; $a++)
echo $arr_number[$a] . " ";
}
$arr_number = array(10, 1045, 765, 91, 02, 524, 66, 27);
$length = count($arr_number);
radixsortalgorithm ($arr_number, $length);
PrintSortedArray($arr_number, $length);
?>

Output:

Example #3: The radix sort algorithm using python language example and output is below.

def count_numberingSort(array_number, e1):
arr_length = len(array_number)
output_number = [0] * (arr_length)
count_number = [0] * (10)
for a in range(0, arr_length):
index_number = (array_number[a] / e1)
count_number[int(index_number % 10)] += 1
for a in range(1, 10):
count_number[a] += count_number[a - 1] a = arr_length - 1
while a >= 0:
index_number = (array_number[a] / e1)
output_number[count_number[int(index_number % 10)] - 1] = array_number[a] count_number[int(index_number % 10)] -= 1
a -= 1
a = 0
for a in range(0, len(array_number)):
array_number[a] = output_number[a] def radixSort(array_number):
max_number = max(array_number)
e = 1
while max_number / e > 0:
count_numberingSort(array_number, e)
e *= 10
array_number = [10, 1045, 765, 91, 2, 524, 66, 27] radixSort(array_number)
for a in range(len(array_number)):
print(array_number[a])

Output:

Conclusion

• The radix sort algorithm removes comparison operation and sort list of number one by one.
• This algorithm helps to sort numbers simply without complexity.
• The radix sort algorithm provides stability to handle array numbers.

Recommended Articles

This is a guide to Radix Sort Algorithm. Here we discuss the Definition, Working procedure of the Radix sort algorithm, examples with code implementation. You may also have a look at the following articles to learn more –

1. Spanning Tree Algorithm
2. Linked List Algorithm
3. DFS Algorithm in C
4. Pseudocode Algorithm