• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 77
  • Last Modified:

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
0
gudii9
Asked:
gudii9
  • 15
  • 8
  • 2
2 Solutions
 
ozoCommented:
When you say "within in a queue", are you saying that you are using sorting to implement a priority queue?
In which case the purpose of the sort seems irrelevant to a question about how a particular type of sort works.
But if you were asking about using queues for the buckets in a Least Significant Digit radix sort, that would seem more like queues within a sort rather than a sort within a queue.

Sorting numbers under 20 then under 40 then under 60 then under 80 etc. sounds more like a radix 20 Most Significant Digit radix sort, which might be done recursively without queues.

This article covers some common implementations of LSD and MSD radix sort http://en.wikipedia.org/wiki/Radix_sort
but if you are implementing a priority queue rather than a standard queue, I don't know that you'd want to do it using a sort, radix or otherwise.  A radix heap may be appropriate, but if you are unsure of how a radix sort works, it may be easier to start with a basic binary heap.
0
 
gudii9Author Commented:
what is LSD and MSD and how those sorts are different. please advise
0
Cloud Class® Course: Microsoft Azure 2017

Azure has a changed a lot since it was originally introduce by adding new services and features. Do you know everything you need to about Azure? This course will teach you about the Azure App Service, monitoring and application insights, DevOps, and Team Services.

 
Tomas Helgi JohannssonCommented:
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
0
 
gudii9Author Commented:
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
0
 
Tomas Helgi JohannssonCommented:
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
0
 
gudii9Author Commented:
it says website not found. please advise
0
 
gudii9Author Commented:
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
0
 
Tomas Helgi JohannssonCommented:
Hi!

See attached pdf file.

Regards,
     Tomas Helgi
18RadixSort.pdf
0
 
gudii9Author Commented:
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
0
 
Tomas Helgi JohannssonCommented:
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
0
 
gudii9Author Commented:
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
0
 
gudii9Author Commented:
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
0
 
Tomas Helgi JohannssonCommented:
HI!

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


Regards,
     Tomas Helgi
0
 
gudii9Author Commented:
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?
0
 
Tomas Helgi JohannssonCommented:
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
0
 
gudii9Author Commented:
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
0
 
Tomas Helgi JohannssonCommented:
Hi!

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

Regards,
    Tomas Helgi
0
 
gudii9Author Commented:
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.
0
 
ozoCommented:
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?
0
 
gudii9Author Commented:
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
0
 
gudii9Author Commented:
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
0
 
gudii9Author Commented:
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
0
 
gudii9Author Commented:
please advise
0
 
gudii9Author Commented:
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
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Upgrade your Question Security!

Your question, your audience. Choose who sees your identity—and your question—with question security.

  • 15
  • 8
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now