Home » Algorithms

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.

  1. Input n number of elements in an array A.
  2. Find the total number of digits in the largest element in the array.
  3. Initialize i=1 and repeat the steps 4 and 5 until( i<=Digit).
  4. Initialize the bucket j=0 and repeat the steps 5until (j<n).
  5. Compare the ith position of each element of the array with bucket number and place it in the corresponding bucket.
  6. Read the elements (S) of the bucket from 0th bucket to 9th bucket and from the first position to the higher one to generate new array A.
  7. Display the sorted array A.
  8. 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

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

Disadvantages of radix sort

  1. 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.
  2. We have to write an unconventional compare routine.
  3. 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

Radix sort example 1

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.

Radix sort example 2

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.

Radix sort example 3

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



Comments and Discussions!





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© some rights reserved.