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
Java EEJavaProgramming Languages-Other

Last Comment
gudii9

8/22/2022 - Mon
ozo

THIS SOLUTION ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform.
SOLUTION
Tomas Helgi Johannsson

THIS SOLUTION ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform.
gudii9

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

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
gudii9

``````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 .

Tomas Helgi Johannsson

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
gudii9

gudii9

not able to access.

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

Hi!

See attached pdf file.

Regards,
Tomas Helgi
gudii9

``````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.

Tomas Helgi Johannsson

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
gudii9

``````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
gudii9

``````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.
Tomas Helgi Johannsson

HI!

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

Regards,
Tomas Helgi
gudii9

``````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?
Tomas Helgi Johannsson

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
gudii9

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)

Tomas Helgi Johannsson

Hi!

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

Regards,
Tomas Helgi
gudii9

``````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.
ozo

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?
gudii9

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.

gudii9

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
gudii9

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

}
``````