radixsort in queues

what is LSD and MSD and how those sorts are different. please advise

Hi!

Least Significant Digit (LSD) and Most Significant Digit (MSD ) this is all covered in the Wiki that we posted.
http://en.wikipedia.org/wiki/Radix_sort
This pdf file (which I posted in earlier comment) shows how LSD and MSD are sorted in a graphic way.
https://www.cs.princeton.edu/~rs/AlgsDS07/18RadixSort.pdf

Regards,
   Tomas Helgi

import java.util.*;
 
/**
 * A sample of base 10 radix sort algorithm.
 */
public class RadixSort {
    // base 10
    // LinkedList is also a Queue
    @SuppressWarnings("unchecked")
    private static LinkedList<Integer>[] counter = new LinkedList[] {
        new LinkedList<Integer>(),
        new LinkedList<Integer>(),
        new LinkedList<Integer>(),
        new LinkedList<Integer>(),
        new LinkedList<Integer>(),
        new LinkedList<Integer>(),
        new LinkedList<Integer>(),
        new LinkedList<Integer>(),
        new LinkedList<Integer>(),
        new LinkedList<Integer>()
    };
 
    public static void sortLSD(int[] array, int maxDigitSymbols) {
        int mod = 10;
        int dev = 1;
        for (int i = 0; i < maxDigitSymbols; i++, dev *= 10, mod *= 10) {
            for(int j = 0; j < array.length; j++) {
                int bucket = (array[j] % mod) / dev;
                counter[bucket].add(array[j]);
            }
            int pos = 0;
            for(int j = 0; j < counter.length; j++) {
                Integer value = null;
                while ((value = counter[j].poll()) != null) {
                    array[pos++] = value;
                }
            }
        }
 
    }
 
    public static void main(String... args) {        
        int[] test = { 10, 1, 30, 156 };
 
        // we choose 3, because we have 156 with 3 digits
        RadixSort.sortLSD(test, 3);
 
        System.out.println(Arrays.toString(test));
    }
 
}

Select allOpen in new window

i see that wiki page ahas only LSD example but not MSD. Where can i find MSD example sample code.

I above LSD example i have below questions.

Why they created multiple instances of linkedlist as below

   private static LinkedList<Integer>[] counter = new LinkedList[] {
        new LinkedList<Integer>(),
        new LinkedList<Integer>(),
        new LinkedList<Integer>(),
        new LinkedList<Integer>(),
        new LinkedList<Integer>(),
        new LinkedList<Integer>(),
        new LinkedList<Integer>(),
        new LinkedList<Integer>(),
        new LinkedList<Integer>(),
        new LinkedList<Integer>()
    };

Select allOpen in new window

also what is happening inside method sortLSD as below

        int mod = 10;
        int dev = 1;
        for (int i = 0; i < maxDigitSymbols; i++, dev *= 10, mod *= 10) {
            for(int j = 0; j < array.length; j++) {
                int bucket = (array[j] % mod) / dev;
                counter[bucket].add(array[j]);
            }
            int pos = 0;
            for(int j = 0; j < counter.length; j++) {
                Integer value = null;
                while ((value = counter[j].poll()) != null) {
                    array[pos++] = value;
                }
            }
        }
 
    

Select allOpen in new window

also

  int[] test = { 10, 1, 30, 156 };
 
        // we choose 3, because we have 156 with 3 digits
        RadixSort.sortLSD(test, 3);
 
        System.out.println(Arrays.toString(test));

what is the test array and why they choose 3 and what is 156 and why are they using toString() method .

please advise

Hi!

The PDF file I mentioned in my earlier comments has both LSD and MSD code examples
as well as good explanation on how it works. ;)

Regards,
     Tomas Helgi

it says website not found. please advise

https://www.cs.princeton.edu/~rs/AlgsDS07/18RadixSort.pdf
not able to access.
it says website not found. please advise.


if possible can you point alternate url or way to get it

Hi!

See attached pdf file.

Regards,
     Tomas Helgi
18RadixSort.pdf

import java.util.*;
 
/**
 * A sample of base 10 radix sort algorithm.
 */
public class RadixSortMSD {
public static void msd(String[] a)
{ 
	msd(a, 0, a.length, 0);
	}
private static void msd(String[] a, int lo, int hi, int d)
{
if (hi <= lo + 1) return;
int[] count = new int[256+1];
for (int i = 0; i < N; i++)
count[a[i].charAt(d) + 1]++;
for (int k = 1; k < 256; k++)
count[k] += count[k-1];
for (int i = 0; i < N; i++)
temp[count[a[i].charAt(d)]++] = a[i];
for (int i = 0; i < N; i++)
a[i] = temp[i];
for (int i = 0; i < 255; i++)
msd(a, l + count[i], l + count[i+1], d+1);
}
 
}

Select allOpen in new window

i got MSD code from pdf but getting compilation errors at N and l etc.

please advise

Hi!

You forgot to initialize N and l should be lo

private static void msd(String[] a, int lo, int hi, int d)
{

int N = a.length();

if (hi <= lo + 1) return;
int[] count = new int[256+1];
for (int i = 0; i < N; i++)
count[a[i].charAt(d) + 1]++;
for (int k = 1; k < 256; k++)
count[k] += count[k-1];
for (int i = 0; i < N; i++)
temp[count[a[i].charAt(d)]++] = a[i];
for (int i = 0; i < N; i++)
a[i] = temp[i];
for (int i = 0; i < 255; i++)
msd(a, lo + count[i], lo + count[i+1], d+1);
}

Select allOpen in new window

Regards,
    Tomas Helgi

public class sssss {

/**
 * @param args
 */
/*public static void main(String[] args) {
	// TODO Auto-generated method stub
	

}
*/

private static void msd(String[] a, int lo, int hi, int d)
{

int N = a.length();

if (hi <= lo + 1) return;
int[] count = new int[256+1];
for (int i = 0; i < N; i++)
count[a[i].charAt(d) + 1]++;
for (int k = 1; k < 256; k++)
count[k] += count[k-1];
for (int i = 0; i < N; i++)
temp[count[a[i].charAt(d)]++] = a[i];
for (int i = 0; i < N; i++)
a[i] = temp[i];
for (int i = 0; i < 255; i++)
msd(a, lo + count[i], lo + count[i+1], d+1);
}

}

Select allOpen in new window

this also has compilation errors

public class sssss {

/**
 * @param args
 */
/*public static void main(String[] args) {
	// TODO Auto-generated method stub
	

}
*/

private static void msd(String[] a, int lo, int hi, int d)
{

int N = a.length;

if (hi <= lo + 1) return;
int[] count = new int[256+1];
for (int i = 0; i < N; i++)
count[a[i].charAt(d) + 1]++;
for (int k = 1; k < 256; k++)
count[k] += count[k-1];
String[] temp;
for (int i = 0; i < N; i++)
temp[count[a[i].charAt(d)]++] = a[i];
for (int i = 0; i < N; i++)
a[i] = temp[i];
for (int i = 0; i < 255; i++)
msd(a, lo + count[i], lo + count[i+1], d+1);
}

}

Select allOpen in new window

i tried above. compiler is still not happy.
please advise

HI!

What does the error tell you ? What does it say ?


Regards,
     Tomas Helgi

public class ssssss {

/**
 * @param args
 */
/*public static void main(String[] args) {
	// TODO Auto-generated method stub
	

}
*/

private static void msd(String[] a, int lo, int hi, int d)
{

int N = a.length;

if (hi <= lo + 1) return;
int[] count = new int[256+1];
for (int i = 0; i < N; i++)
count[a[i].charAt(d) + 1]++;
for (int k = 1; k < 256; k++)
count[k] += count[k-1];
String[] temp = null;
for (int i = 0; i < N; i++)
temp[count[a[i].charAt(d)]++] = a[i];
for (int i = 0; i < N; i++)
a[i] = temp[i];
System.out.println("test....");
for (int i = 0; i < 255; i++)
msd(a, lo + count[i], lo + count[i+1], d+1);
}

}

Select allOpen in new window

it said temp not initialized. I did initialize now.

But i do not see main method so i do not get 'run as java application' option in eclipse. please advise.
is there is a short cout to call particular method to call from main without writing main method and that particular method call?

Hi!

This should do it

public class ssssss {

/**
 * @param args
 */

public static void main(String[] args) {
	// TODO Auto-generated method stub
	String mystr[] =  {"100", "50", "10","1000","400","300","200"};	
	System.out.println(Arrays.toString(mystr));
	msd(mystr);
	System.out.println(Arrays.toString(mystr));
}

public static void msd(String[] a){
	msd(a,0,a.length, 0 );
}


private static void msd(String[] a, int lo, int hi, int d)
{

int N = a.length;

if (hi <= lo + 1) return;
int[] count = new int[256+1];
for (int i = 0; i < N; i++)
count[a[i].charAt(d) + 1]++;
for (int k = 1; k < 256; k++)
count[k] += count[k-1];
String[] temp = null;
for (int i = 0; i < N; i++)
temp[count[a[i].charAt(d)]++] = a[i];
for (int i = 0; i < N; i++)
a[i] = temp[i];
System.out.println("test....");
for (int i = 0; i < 255; i++)
msd(a, lo + count[i], lo + count[i+1], d+1);
}

}

Select allOpen in new window

Regards,
   Tomas Helgi

i tried getting null pointer from below line

temp[count[a[i].charAt(d)]++] = a[i];

Select allOpen in new window

package jdbc;

import java.util.Arrays;

public class ssssss {

	/**
	 * @param args
	 */

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String mystr[] = { "100", "50", "10", "1000", "400", "300", "200" };
		System.out.println(Arrays.toString(mystr));
		msd(mystr);
		System.out.println(Arrays.toString(mystr));
	}

	public static void msd(String[] a) {
		msd(a, 0, a.length, 0);
	}

	private static void msd(String[] a, int lo, int hi, int d) {

		int N = a.length;

		if (hi <= lo + 1)
			return;
		int[] count = new int[256 + 1];
		for (int i = 0; i < N; i++)
			count[a[i].charAt(d) + 1]++;
		for (int k = 1; k < 256; k++)
			count[k] += count[k - 1];
		String[] temp = null;
		for (int i = 0; i < N; i++)
			temp[count[a[i].charAt(d)]++] = a[i];
		for (int i = 0; i < N; i++)
			a[i] = temp[i];
		System.out.println("test....");
		for (int i = 0; i < 255; i++)
			msd(a, lo + count[i], lo + count[i + 1], d + 1);
	}

}

Select allOpen in new window

[100, 50, 10, 1000, 400, 300, 200]
Exception in thread "main" java.lang.NullPointerException
      at jdbc.ssssss.msd(ssssss.java:36)
      at jdbc.ssssss.msd(ssssss.java:20)
      at jdbc.ssssss.main(ssssss.java:15)

please advise

Hi!

Line 34 needs to be
String[] temp = new String[a.length];

Regards,
    Tomas Helgi

import java.util.Arrays;

public class ssssss {

	/**
	 * @param args
	 */

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String mystr[] = { "100", "50", "10", "1000", "400", "300", "200" };
		System.out.println(Arrays.toString(mystr));
		msd(mystr);
		System.out.println(Arrays.toString(mystr));
	}

	public static void msd(String[] a) {
		msd(a, 0, a.length, 0);
	}

	private static void msd(String[] a, int lo, int hi, int d) {

		int N = a.length;

		if (hi <= lo + 1)
			return;
		int[] count = new int[256 + 1];
		for (int i = 0; i < N; i++)
			count[a[i].charAt(d) + 1]++;
		for (int k = 1; k < 256; k++)
			count[k] += count[k - 1];
		//String[] temp = null;
		String[] temp = new String[a.length];
		for (int i = 0; i < N; i++)
			temp[count[a[i].charAt(d)]++] = a[i];
		for (int i = 0; i < N; i++)
			a[i] = temp[i];
		System.out.println("test....");
		for (int i = 0; i < 255; i++)
			msd(a, lo + count[i], lo + count[i + 1], d + 1);
	}

}

Select allOpen in new window

i tried as above now getting error as below

[100, 50, 10, 1000, 400, 300, 200]
test....
test....
Exception in thread "main" java.lang.StringIndexOutOfBoundsException
      at java.lang.String.charAt(String.java:465)
      at ssssss.msd(ssssss.java:31)
      at ssssss.msd(ssssss.java:42)
      at ssssss.msd(ssssss.java:42)
      at ssssss.msd(ssssss.java:20)
      at ssssss.main(ssssss.java:15)


please advise.  I wonder why the temp needs to be initialized with lenght.

when i=1 and d=2,
a[ i]=10
and there is no a[ i].charAt(2)
What do you want to do in such cases?

when i=1 and d=2,
a[ i]=10
and there is no a[ i].charAt(2)

how you go to the root and bottom of problem quickly. please teach me that skill.

let me think answer

what is i and what is d here

and there is no a[ i].charAt(2)

why there is no abovee one?

i do not know what to do, i just want to run this example to see radix concept in working

import java.util.Arrays;

public class ssssss {

	/**
	 * @param args
	 */

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String mystr[] = { "100", "50", "10", "1000", "400", "300", "200" };
		System.out.println(Arrays.toString(mystr));
		msd(mystr);
		System.out.println(Arrays.toString(mystr));
	}

	public static void msd(String[] a) {
		msd(a, 0, a.length, 0);
	}

	private static void msd(String[] a, int lo, int hi, int d) {

		int N = a.length;

		if (hi <= lo + 1)
			return;
		int[] count = new int[256 + 1];
		for (int i = 0; i < N; i++)
			count[a[i].charAt(d) + 1]++;
		for (int k = 1; k < 256; k++)
			count[k] += count[k - 1];
		//String[] temp = null;
		String[] temp = new String[a.length];
		for (int i = 0; i < N; i++)
			temp[count[a[i].charAt(d)]++] = a[i];
		for (int i = 0; i < N; i++)
			a[i] = temp[i];
		System.out.println("test....");
		for (int i = 0; i < 255; i++)
			msd(a, lo + count[i], lo + count[i + 1], d + 1);
	}

}

Select allOpen in new window

not sure how to fix above code. please advise
debug1.jpg
debug2.jpg

please advise

http://cs.stackexchange.com/questions/40364/i-can-not-see-why-msd-radix-sort-is-theoretically-as-efficient-as-lsd-radix-sort

i saw one discussion here but not complete code example without any errors anywhere on internet. please advise