## Radix Sort for positive integer

Back to Programming

### Description

Radix sort is a sorting technique which is different from the concept of bubble, selection, merge or quick sort as radix sort is done by depending on the digits of the elements from the right most bit to the left most bit and by sorting the positional digits the sorting is performed. Unlike the other commonly used sorting algorithms, radix sort is a non-comparison based sorting algorithm. It depends on the place values of the numbers and grouped together according to the place values and thus sorting is performed.

PROCEDURE WITH EXAMPLE:

Suppose an array of 7 elements is taken to perform radix sort as follows:

Now, this array is to be sorted. Before sorting the array the number of digits in the maximum element is to be found out. In this case, the maximum element of this array is 654 and the number of digits if this element is 3. So the number of passes required to sort is 3.

## Pass 1:

In the first pass the right most digits of the element is considered and will be sorted according to those digits and we will get the array as:

## Pass 2:

After the first pass, the array is sorted according to the right most digit of the elements and the array is:

Now in the second pass the 2nd digit from the right side will be considered and will be sorted according to those digits underlined in the above array. Now the array will be sorted and the new array will be:

Now, the array is sorted according to the 2nd digit (from the right side) of each element of the array.

## Pass 3:

This is the last pass to sort the elements of the array, so here the array will be sorted according to the most significant bit that is the left most bit of each element. The elements which are of 2 digits, for that elements the 3rd bit from the right side is not available, hence ‘0’ will be considered as the most significant bit of the elements as follows:

So the final sorted array will be:

### Algorithm

``````INPUT:An unsorted array a[6,2,4,1,…………….,n]
OUTPUT:  An sorted array a[1,2,3,4,5,…………..,n] (in ascending order)

Step 1: Create a function “void radixsort(int a[],int n)”
Step 1.1: Set or initialise the all elements of an integer type array ‘d’ at 0 i.e
Set  d[i] <- 0 [ i= 0 to 9]
Step 1.2: Take the max number of digit in an integer type variable ‘max’ and this is the number          of required pass to do the sorting.
Step 1.3: While(pass ≤ max) then repeat  Step 1.4 to Step 1.22
Step 1.4: For i=0 to i<n  repeat  Step 1.5 to Step 1.13
Step 1.5:  Set  c <- 0
Step 1.6:  Set  p <- a[i]
Step 1.7: While(c<pass) then  repeat  Step  1.8 to Step 1.10
Step 1.8:  Set  r <- p mod 10
Step 1.9:  Set  p <- p/10
Step 1.10: Set  c <- c+1
[End of Step 1.7 ‘While’ loop]
Step 1.11:  Set  j <- d[r]
Step 1.12:  Set  b[r][j] <- a[i]
Step 1.13:  Set  d[r] <- d[r]+1
[End of Step 1.4 ‘For’ loop]
Step 1.14:  Set  pass <- pass+1
Step 1.15:  Set I <- 0
Step 1.16: For  j=0 to 9 repeat Step 1.17 to Step 1.20
Step 1.17: If(d[j]>0) then do
Step 1.18: For  k=0 to k<d[j] repeat  Step 1.19 and Step 1.20
Step 1.19: Set  a[i] <- b[j][k]
Step 1.20: Set  I <- i+1
[End of  Step 1.18 ‘For’ loop]
[End of ‘If’]
[End of Step 1.16 ‘For’ loop]
Step 1.21: For i=0 to 9 repeat Step 1.22
Step 1.22: Set d[i] <- 0
[End of 1.3 ‘While’ loop]
[End of the function “void radixsort(int a[],int n)”]

Step 2: Create the function “void main()”

Step 2.1 Take the number of elements from the user in an integer type variable ‘n’ .
Step 2.2: Take the unsorted elements from the user in an array ‘a’.
Step 2.3: Print the unsorted array.
Step 2.4: Call the function ‘radixsort(a,n)’
Step 2.5: Print the sorted array ‘a’.
Step 2.6: Stop.
[End of the function “void main()”]

Step 3: Stop.
``````

### Code

CHARACTERISTICS:

1. It is a non-comparison based sorting technique.

2. It is performed by performing a multi-pass bucket sort.

3. It is a straight sorting algorithm.

4. It is not an in-place sorting algorithm.

5. It is a stable sorting algorithm.

6. It is a linear sorting algorithm.

TIME COMPLEXITY:

The best case, average case, and worst-case complexity are the same in the case of radix sort as it is a non-comparison based sorting technique.

The time complexity of radix sort is O(k.n) where n is a number of integer elements of word size k.

SPACE COMPLEXITY:

The total space required to sort the data is O(n + k) where is the number of elements and is the range of data (or word size).

APPLICATIONS:

1. Radix sorts are used mostly to the collections of binary strings and integers to sort.

2. Radix sort can be parallelized or can be implemented in parallel computing easily.

1. The sorting is done by straight calculation.

2. It is a steady sort.

3. The complexity is almost the same as the other sorting algorithms but the calculation in radix sort is simpler than the others.

1. It requires extra spaces for intermediate sort.

3. It is quite complex to program for a wide assortment of usefulness.

4. The above algorithm only works for the positive data only as it is sorted according to the place values but the elements are not compared with each other.

5. We will get better complexity to compare to comparative sorting but it only true for 32-bit and 64-bit digits numbers. For more digits, it does not give the linear time complexity

Related