Page Contents

Radix sort is a **non-comparative **sorting algorithm that sorts elements digit by digit starting from least significant digit to most significant digit.

Suppose if you want to sort 10 elements in ascending order using radix sort, first sort the digit of unit place. After that sort the tenth place digit. This process will go till the most significant digits.

Let’s see an example to understand it clearly

Suppose we have 7 elements in an array.

**{101, 45,543,233,321, 833,432}**

After sorting unit digit our array will look like

**{101, 321,432, 543, 233, 833, 45}**

Radix sort uses counting sort as an intermediate sort.

## How does radix sort work?

- First Find the largest element in the array. In our case array is {101, 45, 543, 233, 212, 654, 833} and the maximum number in the array is 833 which has 3 digits.
- We find maximum because we have to go up to the most significant digit which is calculated by a total number of digits of the maximum number. The maximum number is
**833**and the total number of the digit in**833**is**‘3’**. so the loop will go up to a hundred places. - Visit each significant place one by one from least significant digits to most significant digits. Here we sort elements of each signification digits using counting sort which is non-comparison sorting.

Let’s see a step-wise procedure how to sort elements using radix sort.

With the help of algorithm we will sort the unit digit of the input array i.e. least significant digit

So after first pass array will become

Now we will sort the tenth digit place of the input array

So after the second pass array will look like

Now we will sort the 100th digit place of the input array i.e. most significant place

After the third pass array will be sorted

## Radix Sort Algorithm

**Step 1:** Find the maximum number in ARR as Max**Step 2:** Calculate the Number of digits in Max and SET NOS = number of digit**Step 3:** Repeat Step 4 to 8 for PASS = 1; PASS <= NOS**Step 4:** Repeat Step 5 to 7for I=0 to I < Size of ARR**Step 5:** SET DIGIT = Arr[I]**Step 6:** Insert element Arr[I] to the bucket at index DIGIT**Step 7:** Do Increment in bucket count for index DIGIT

[END OF FOR Loop]**Step 8:** Pick elements from the bucket starting from index 0 and put in ARR

[END OF For LOOP]**Step 9:** END

## Radix Sort Complexity

### Radix sort time complexity

**Best-case performance**: O(n)**Average Performance**: O(n)

**Worst-case performance**: O(n)

### Radix sort space complexity

**Space complexity:** O(n+k)

## Radix Sort Program in C

// Radix Sort in C Programming

#include

void countingSort(int arr[], int size, int place) {

int i,range=10;

int freq[10]={0};

int output[size];

for(i=0;i

{

output[freq[(arr[i]/place)%range]-1]=arr[i];

freq[(arr[i]/place)%range]–;

}

for(i=0;i

max = array[i];

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

countingSort(array, size, place);

}

int main(){

int arr[100],i,j,n,key;

printf(“Radixsort Program in C\n”);

printf(“Enter the number of elements you want to sort:\n”);

scanf(“%d”,&n);

printf(“Now enter the %d elements you want to sort: \n”,n);

for(i=0;i

**Output : **

Share On :