I\'m supposed to make a Radix Sort using a queue and this is what I have: RadixS
ID: 3601390 • Letter: I
Question
I'm supposed to make a Radix Sort using a queue and this is what I have:
RadixSort Class:
public class RadixSort {
int[] array={304,319,819,1420,9201,1212,4102,8196,1076,1331,1471,2193,1055};
Queue[] digits=new Queue[13];
public RadixSort(){
System.out.println("Unsorted array:");
printArray();
for(int i=0;i<digits.length;i++){
digits[i]=new Queue(i);
}
for(int i=0;i<array.length;i++){
System.out.println(findLSD(array[i]));
digits[findLSD(array[i])].enque(array[i]);
}
printQueue();
array=new int[13];
int z=0;
for(int i=0;i<digits.length;i++){
while(!digits[i].isEmpty()){
System.out.println("i:"+i+" z:"+z);
array[z]=digits[i].getFront();
digits[i].deque();
z++;
}
}
System.out.println("Array after 1st sorting: ");
printArray();
for(int i=0;i<array.length;i++){
System.out.println(findLSD(array[i]));
digits[findTens(array[i])].enque(array[i]);
}
printQueue();
}
public static void main(String args[]){
RadixSort rs=new RadixSort();
}
int findLSD (int number){
return number % 10;
}
int findTens(int number){
return (number % 100)/10;
}
void printArray(){
for (int num: array){
System.out.print(num + " ");
}
}
void printQueue(){
for(int i=0;i<digits.length;i++){
System.out.println("Queue "+i+": "+digits[i]);
}
}
}
Queue Class:
public class Queue{
private int[] array;
private int Max;
private int front, rear, count=0;
public Queue(int size){
Max=size;
front=rear=0;
count=0;
array=new int[size];
}
public int getSize()
{
return count;
}
public boolean isEmpty(){
return count==0;
}
public void enque(int a){
if(count+1<=Max){
array[rear]=a;
rear++;
count--;
System.out.println(a + " Was added to the rear");
}
else{
System.out.println("Queue Full");
}
}
public void deque(){
if(count>0){
System.out.println(array[front] + " Was removed from the front");
array[front]=-1;
front++;
count--;
}
else{
System.out.println("Queue empty");
}
}
public int getFront(){
return front;
}
public void display(){
System.out.println("Queue: ");
for (int i=0;i<Max;i++){
System.out.print(array[i]+i);
System.out.println();
}
}
}
This is the output:
Unsorted array:
249 219 789 110 911 112 518 816 176 167 671 233 455 9
249 Was added to the rear
9
219 Was added to the rear
9
789 Was added to the rear
0
Queue Full
1
911 Was added to the rear
2
112 Was added to the rear
8
518 Was added to the rear
6
816 Was added to the rear
6
176 Was added to the rear
7
167 Was added to the rear
1
Can someone explain the problem?
Explanation / Answer
See, we have given numbers as
304,319,819,1420,9201,1212,4102,8196,1076,1331,1471,2193,1055
Step 1: We will sort using the last digits
304 last digit is 4 ,
319 last digit is 9 , ......
In this way we will get the first pass after sorting as
1420 , 9201, 1331,1471, 1212, 4102,2193, 304, 1055,8196 , 1076 , 319, 819
Step 2: We will sort using the 2nd last digits
304 2nd last digit is 0 ,
319 2nd last digit is 1 , ......
In this way we will get the 2nd pass after sorting as
9201, 304,1212,319, 819,1420 ,1331, 1055,1471, 1076 ,8196 ,2193
Step 2: We will sort using the 3rd last digits
304 3rd last digit is 3 ,
319 3rd last digit is 3 , , ......
In this way we will get the 2nd pass after sorting as
1055, 1076, 2193 , 9201, 1212, 304,319, 1331, 1420 ,1471, ,819 , 8196
Final pass :
306 will have digit 0 in 3th position from left
Final Pass after considering the first most digit
304 , 319 , 819 , 1055 , 1076 , 1212, 1331, 1420, 1471, 2193, 8196, 9201
Like this way we got Sorted Order