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
ozo

membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION

membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.

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.
This pdf file (which I posted in earlier comment) shows how LSD and MSD are sorted in a graphic way.

Regards,
Tomas Helgi

``````import java.util.*;

/**
* A sample of base 10 radix sort algorithm.
*/
// base 10
// LinkedList is also a Queue
@SuppressWarnings("unchecked")
};

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

System.out.println(Arrays.toString(test));
}

}``````

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[] {
};``````

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;
}
int pos = 0;
for(int j = 0; j < counter.length; j++) {
Integer value = null;
while ((value = counter[j].poll()) != null) {
array[pos++] = value;
}
}
}

``````

also

int[] test = { 10, 1, 30, 156 };

// we choose 3, because we have 156 with 3 digits

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 .

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

not able to access.

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

See attached pdf file.

Regards,
Tomas Helgi

``````import java.util.*;

/**
* A sample of base 10 radix sort algorithm.
*/
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);
}

}``````

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

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

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

}``````

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

}``````

i tried above. compiler is still not happy.
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);
}

}``````

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

}``````

Regards,
Tomas Helgi

i tried getting null pointer from below line

``temp[count[a[i].charAt(d)]++] = a[i];``
``````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);
}

}``````
[100, 50, 10, 1000, 400, 300, 200]
at jdbc.ssssss.msd(ssssss.java:36)
at jdbc.ssssss.msd(ssssss.java:20)
at jdbc.ssssss.main(ssssss.java:15)

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

}``````

i tried as above now getting error as below

[100, 50, 10, 1000, 400, 300, 200]
test....
test....
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.

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

}``````