Sorting

Radix sort

Pinterest LinkedIn Tumblr

Radix sort is a linear sorting algorithm that sorts data by grouping keys. The individual digits which share the same significant position and value.

Radix sort helps to sort fixed length words. Radix sort requires fixed size key and difficult to generalize. It can use with integers, fixed size strings, and “less than”, “greater than” or “lexicographic order” comparison predicates.

Two classifications of radix sorts are least significant digit (LSD) radix sorts and most significant digit (MSD) radix sorts. LSD radix sorts process the integer representations starting from the least digit and moves towards the most significant digit. MSD radix sorts work the other way around. LSD radix sort typically uses for sorting the keys in ascending order with same key length. MSD radix sort typically uses for sorting strings with fixed length.

Radix sorts are often, in practice, the fastest and most useful sorts on parallel machines. Write a program to implement radix sort.

source Code

package com.dsacode.Algorithm.sorting;
 
import java.util.Arrays;
 
public class RadixSort {
 
     public static void sort( int[] a)  {
            int i, m = a[0], exp = 1, n = a.length;
            int[] b = new int[10];
            for (i = 1; i < n; i++)
                if (a[i] > m)
                    m = a[i];
            while (m / exp > 0) {
                int[] bucket = new int[10];
      
                for (i = 0; i < n; i++)
                    bucket[(a[i] / exp) % 10]++;
                for (i = 1; i < 10; i++)
                    bucket[i] += bucket[i - 1];
                for (i = n - 1; i >= 0; i--)
                    b[--bucket[(a[i] / exp) % 10]] = a[i];
                for (i = 0; i < n; i++)
                    a[i] = b[i];
                exp *= 10;       
            }
        }   
         
        public static void main(String []args){
            int[] arr={12,34,56,23,45,78,46};
            System.out.println("unsorted array before sorting : " + Arrays.toString(arr));
            sort(arr);
            System.out.println("Sorted array After RadixSort sorting : " + Arrays.toString(arr));
        }
}

Output

Unsorted array before sorting: [12, 34, 56, 23, 45, 78, 46]
Sorted array After Radix Sort sorting: [12, 23, 34, 45, 46, 56, 78]

Algorithm Explanation

Get the maximum element from the array.
Partition the list into buckets by the most significant digit.
Recursively use Radix Sort each non-empty bucket.
Concatenate the results and Return the sorted array.

Time Complexity

Best CaseAverage CaseWorst Case
O(nk)O(nk)O(wn)

Reference

  1. https://www.cs.usfca.edu/~galles/visualization/RadixSort.html
  2. https://en.wikipedia.org/wiki/Radix_sort
  3. https://www.youtube.com/watch?v=xhr26ia4k38

Write A Comment