Sorting

Least Significant Digit (LSD) radix sort

Pinterest LinkedIn Tumblr

Least Significant Digit (LSD) radix sort process the integer representations starting from the least digit and moves towards the most significant digit. Radix sort is a linear sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value.

LSD radix sorts process the integer representations starting from the least digit and moves towards the most significant digit. LSD radix sort is a stable sort. If there are multiple elements to sort with the same key, they’ll end up in the same relative order in the sorted output when you run LSD radix sort. The biggest advantage of LSD radix sort is speed because it is a branch-free algorithm.

Write a program to implement LSD radix sort

source Code

package com.dsacode.Algorithm.sorting;
 
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
 
public class LSDRadixsort {
 
    public static void radixSort(int[] arr)
    {
        @SuppressWarnings("unchecked")
        Queue < Integer > [] buckets = new Queue[10];
         
        for (int i = 0; i < 10; i++)
            buckets[i] = new LinkedList < Integer >();
 
        boolean sorted = false;
        int expo = 1;
 
        while ( ! sorted) {
            sorted = true;
 
            for (int item : arr) {
                int bucket = (item / expo) % 10;
                if (bucket > 0) sorted = false;
                buckets[bucket].add(item);
            }
 
            expo *= 10;
            int index = 0;
 
            for (Queue < Integer > bucket : buckets)
                while ( ! bucket.isEmpty())
                    arr[index++] = bucket.remove();
        }
 
       
    }
     
    public static void main(String[] args) {
        int []arr={34,56,23,88,67,89};
         
        System.out.println("List of items from array before sorting: "+ Arrays.toString(arr));
      
        radixSort(arr);
        System.out.println("List of items from array after sorting: "+ Arrays.toString(arr));
 
    }
 
}

Output

List of items from array before sorting: [34, 56, 23, 88, 67, 89]
List of items from array after sorting: [23, 34, 56, 67, 88, 89]

Algorithm Explanation

Sort by the least significant digit of the key, usually with CountingSort or BucketSort.
Repeat for the rest of the digits, working up to the MSD.
Ordering from the previous iterations remain
Print the Sorted array.

Time Complexity

Best CaseAverage CaseWorst Case
WNWN

Reference

  1. https://en.wikipedia.org/?title=Radix_sort
  2. https://www.cs.princeton.edu/~rs/AlgsDS07/18RadixSort.pdf

Write A Comment