# Radix Sort and its Algorithm

In this article, we are going to discuss about the **radix sort, its algorithm**, time complexity of radix sort and also some advantages and disadvantages of radix sort.

Submitted by Prerana Jain, on June 30, 2018

## Radix Sort

**Radix sort or bucket sort** is a method that can be used to sort a list of a number by its base. If we want to sort the list of English words, where radix or base is 26 then 26 buckets are used to sort the words.

To sort an array of decimal number where the radix or base is 10 we need 10 buckets and can be numbered as 0,1,2,3,4,5,6,7,8,9. A number of passes required to have a sorted array depend upon the number of digits in the largest element.

## Algorithm for Radix sort

Let **A** be a linear array of **n** elements **A[1], A[2], A[3]............A[n]**. Digit is the total number of digit in the largest element in array **A**.

- Input n number of elements in an array A.
- Find the total number of digits in the largest element in the array.
- Initialize i=1 and repeat the steps 4 and 5 until( i<=Digit).
- Initialize the bucket j=0 and repeat the steps 5until (j<n).
- Compare the i
^{th}position of each element of the array with bucket number and place it in the corresponding bucket. - Read the elements (S) of the bucket from 0
^{th}bucket to 9^{th}bucket and from the first position to the higher one to generate new array A. - Display the sorted array A.
- Exit.

**Time complexity**

Time requirement for the **radix sorting method** depends on the number of digits and the elements in the array. Suppose **A** is an array of **n** elements **A1, A2...** An and let **r** denote the radix( for example **r=10** for decimal digits, **r=26** for English letters and **r=2** for hits). If **A1** is the largest number then **A!** Can be represented. Then **radix sort** require **s** passes. In passes, each element is compared with the bucket elements.

So the **radix sort** requires the total comparison **f(n)** of: **F(n) < = r x s x n**

**Worst case**

In the worst case **s = n** so **F(n) = O(n2)**

**Best case**

In the best case **s = logn** so **f(n) = (nlogn)**

**Average case**

It is very hard to define the time complexity. Because it will depend on the choice of the radix **r** and also the number of a digit on largest elements (i.e number of passes) but on an average (**log n**) comparison is required so **f(n) = O(nlogn)**

### Advantages of radix Sort

- It is implemented in Java, it would be faster than quicksort or heap.
- It is stable because it preserves existing order of equals keys.
- It is good on small keys.

### Disadvantages of radix sort

- It is not efficient on very long keys because the total sorting time is proportional to key length and to the number of items to sort.
- We have to write an unconventional compare routine.
- It requires fixed size keys and some standard way of breaking the keys to pieces.

**Example:** To illustrate the radix sort consider the following array with 7 elements

42, 133, 7, 23, 74, 670, 49

In this array, the biggest elements are 670 and the number of digits is 3, so 3 passes are required to sort the array. Read the elements and compare the first position (2 is in the first position of 42) digits with the digits of the buckets and place it

Now read the elements from left to right and the bottom to the top of the bucket and place it in an array for the next pass. Read the array elements and compare the second position (4 is in the second position of the elements 042) digit with a number of the bucket and place it.

Again read the element from left to right and from bottom to top to get an array for the third pass. (0 is in the first position of 042) compare the third position digit in each element with the budget digit and place it wherever it matches.

**Now the sorted array is 7 , 23, 42, 49, 74, 133, 670.**

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions