Link to home
Start Free TrialLog in
Avatar of gudii9
gudii9Flag for United States of America

asked on

radixsort in queues

Hi,

I would like to understand how the radix  sort works within in a queue. If i have set of say 100 numbers it is able to sort numbers under 20 then under 40 then under 60 then under 80 etc right? How Radix Sort achieves it and what is the internal alogithm it uses. please advise
ASKER CERTIFIED SOLUTION
Avatar of ozo
ozo
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of gudii9

ASKER

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
Avatar of gudii9

ASKER

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));
    }
 
}

Open 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>()
    };

Open 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;
                }
            }
        }
 
    

Open 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
Avatar of gudii9

ASKER

it says website not found. please advise
Avatar of gudii9

ASKER

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
Avatar of gudii9

ASKER

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);
}
 
}

Open 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);
}

Open in new window


Regards,
    Tomas Helgi
Avatar of gudii9

ASKER

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);
}

}

Open in new window


this also has compilation errors
Avatar of gudii9

ASKER

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);
}

}

Open 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
Avatar of gudii9

ASKER

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);
}

}

Open 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);
}

}

Open in new window


Regards,
   Tomas Helgi
Avatar of gudii9

ASKER

i tried getting null pointer from below line

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

Open 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);
	}

}

Open 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
Avatar of gudii9

ASKER

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);
	}

}

Open 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?
Avatar of gudii9

ASKER

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
Avatar of gudii9

ASKER

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
Avatar of gudii9

ASKER

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);
	}

}

Open in new window


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

ASKER

please advise
Avatar of gudii9

ASKER

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