Sorting

Most Significant Digit (MSD) radix sort

Pinterest LinkedIn Tumblr

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.

Most Significant Digit (MSD) radix sort typically uses for sorting strings with fixed length. MSD radix sorts process the integer representations starting from the most digit and moves towards the least significant digit.

Write a program to implement MSD radix sort?

source Code

package com.dsacode.Algorithm.sorting;
 
import java.util.Arrays;
 
public class MSDRadixSort {
    private static final int R      = 256;  
    private static final int CUTOFF =  15;  
 
    public static void sort(String[] a) {
        int N = a.length;
        String[] aux = new String[N];
        sort(a, 0, N-1, 0, aux);
    }
 
    private static int charAt(String s, int d) {
        if (d == s.length())
            return -1;
        return s.charAt(d);
    }
 
    private static void sort(String[] a, int lo, int hi, int d, String[] aux) {
 
        if (hi <= lo + CUTOFF) {
            insertion(a, lo, hi, d);
            return;
        }
 
        int[] count = new int[R+2];
        for (int i = lo; i <= hi; i++) {
            int c = charAt(a[i], d);
            count[c+2]++;
        }
 
        for (int r = 0; r < R+1; r++)
            count[r+1] += count[r];
 
        for (int i = lo; i <= hi; i++) {
            int c = charAt(a[i], d);
            aux[count[c+1]++] = a[i];
        }
 
        for (int i = lo; i <= hi; i++)
            a[i] = aux[i - lo];
 
 
        for (int r = 0; r < R; r++)
            sort(a, lo + count[r], lo + count[r+1] - 1, d+1, aux);
    }
 
 
    private static void insertion(String[] a, int lo, int hi, int d) {
        for (int i = lo; i <= hi; i++)
            for (int j = i; j > lo && less(a[j], a[j-1], d); j--)
                exch(a, j, j-1);
    }
 
    private static void exch(String[] a, int i, int j) {
        String temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
 
    private static boolean less(String v, String w, int d) {
        assert v.substring(0, d).equals(w.substring(0, d));
        return v.substring(d).compareTo(w.substring(d)) < 0;
    }
     
    public static void main(String[] args) {
        String[] a = {"Hello","world","java","j2ee"};
        System.out.println("List of items from array before sorting: " + Arrays.toString(a));
        sort(a);
        System.out.println("List of items from array after sorting: " + Arrays.toString(a));
 
    }
 
}

Output

List of items from array before sorting: [Hello, world, java, j2ee]
List of items from array after sorting: [Hello, j2ee, java, world]

Algorithm Explanation

Partition the list into buckets by the most significant digit.
Recursively MSD RadixSort each non-empty bucket.
OConcatenate the results and display the sorted array.

Time Complexity

Best CaseAverage CaseWorst Case
W( N+R)

Reference

  1. http://www.cs.helsinki.fi/u/tpkarkka/opetus/10s/spa/lecture06.pdf
  2. https://en.wikipedia.org/?title=Radix_sort

3 Comments

  1. Hello there, There’s no doubt that your website could possibly be having web browser compatibility issues.
    When I look at your website in Safari, it looks fine however,
    if opening in I.E., it’s got some overlapping issues. I simply wanted to provide you
    with a quick heads up! Aside from that, great site!

  2. obviously like your web-site however you need to take a look at the spelling on quite a few of your posts. A number of them are rife with spelling issues and I to find it very troublesome to tell the truth however I will definitely come again again.

Write A Comment