Use class Queue. java you developed in part I above to implement the Radix Sort

Question

Use class Queue. java you developed in part I above to implement the Radix Sort algorithm using queues. Call the program RadixSort. java. The program prompts the user to enter 6 integer numbers and store them in an array that stores integers (call it inputs). The program applies radix sort to the values stored in the array and then prints out the content of array inputs before and after being sorted. For example, if the user entered the numbers 213, 3465, 7, 29, 541, 45, the program output would be as follows: Notice that we are using ONLY one array, and your need 10 queue objects to implement radix sort. See class notes. For digit extraction required for radix sort, implement a separate method in class RadixSort (call it ExtractDigit (...)) to do this function. See class notes on how to do digit extraction.

Explanation / Answer

import java.util.Scanner;

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

/**
*
* @author Surya
*/
class queue
{
long v[];
int size=0;
queue()
{
v= new long[100];//queue capacity to store hundred integers
//you can increase the capcity
}
  
}

public class radixSort {
  
void print_array(long a[])
{
int i;
int n =a.length;

for(i=0;i<n;i++)
{
System.out.print(a[i]+" ");
}
System.out.println();
}
  
int getMax(long a[])//method to find max in a given array and counts its digits and return it,
{
long max=a[0];
int n = a.length;
int i;

for(i=0;i<n;i++)
{
if(a[i]>max)max = a[i];
}
int c=0;
while(max>0)
{
max=max/10;
c++;
}

return c;
}
  
long extractDigit(long n,int p)//method to etract digit at givenposition from least significant bit...
{ //p -position
int i=0;
for(i=0;i<p-1;i++)
{
n=n/10;
}
return n%10;
}
  
  
void radix_sort(long a[])
{
queue zero,one,two,three,four,five,six,seven,eight,nine;
zero =new queue();//10 queue..objects
queue();
two =new queue();
three =new queue();
four =new queue();
five =new queue();
six =new queue();
seven =new queue();
eight =new queue();
nine =new queue();
  
int max = this.getMax(a);
  
int i=1,j;
int n =a.length;
long digit;
//digit wise forming buckets in queues...
while(i<=max)
{
  
for(j=0;j<n;j++)
{
  
digit = this.extractDigit(a[j], i);
  
//adding to appropriate bucket queue
if(digit == 0)
{
zero.v[zero.size]=a[j];
zero.size++;
}
else if(digit ==1)
{
one.v[one.size]=a[j];
one.size++;
}
else if(digit ==2)
{
two.v[two.size]=a[j];
two.size++;
  
}
else if(digit ==3)
{
  
three.v[three.size]=a[j];
three.size++;
}
else if(digit ==4)
{
  
four.v[four.size]=a[j];
four.size++;
}
else if(digit ==5)
{
five.v[five.size]=a[j];
five.size++;
}
else if(digit ==6)
{
six.v[six.size]=a[j];
six.size++;
  
}
else if(digit ==7)
{
seven.v[seven.size]=a[j];
seven.size++;
}
else if(digit ==8)
{
eight.v[eight.size]=a[j];
eight.size++;
}
else if(digit ==9)
{
nine.v[nine.size]=a[j];
nine.size++;
}
  
  
  
}
  
  
j=0;
int c=0;
//emptying queues..
while(c<zero.size)
{
a[j]=zero.v[c];
j++;
c++;
}
zero.size=0;
  
  
c=0;
while(c<one.size)
{
a[j]=one.v[c];
j++;
c++;
}
one.size=0;
  
  
c=0;
while(c<two.size)
{
a[j]=two.v[c];
j++;
c++;
}
two.size=0;
  
  
c=0;
while(c<three.size)
{
a[j]=three.v[c];
j++;
c++;
}
three.size=0;
  
  
c=0;
while(c<four.size)
{
a[j]=four.v[c];
j++;
c++;
}
four.size=0;
  
  
c=0;
while(c<five.size)
{
a[j]=five.v[c];
j++;
c++;
}
five.size=0;
  
  
c=0;
while(c<six.size)
{
a[j]=six.v[c];
j++;
c++;
}
six.size=0;
  
  
c=0;
while(c<seven.size)
{
a[j]=seven.v[c];
j++;
c++;
}
seven.size=0;
  
  
c=0;
while(c<eight.size)
{
a[j]=eight.v[c];
j++;
c++;
}
eight.size=0;
  
c=0;
while(c<nine.size)
{
a[j]=nine.v[c];
j++;
c++;
}
nine.size=0;
  
  
  
  
  
  
i++;
}
  

  
  
  
  
}
  
//test program
public static void main(String argv[])
{
long a[] = new long[6];
int i;
System.out.println("Enter 6 numbers:");
Scanner sc = new Scanner(System.in);
  
for(i=0;i<6;i++)
{
a[i] = sc.nextInt();//reading integers..
}
  
  
//creating objects...
radixSort r = new radixSort();
  
System.out.print("printing array before sorting : ");
r.print_array(a);
  
//sorting array
r.radix_sort(a);
  
System.out.print("printing array after sorting : ");
r.print_array(a);
  
  
}
  
  
  
  
}

output:-

run:
Enter 6 numbers:
213
3465
7
29
541
45
printing array before sorting : 213 3465 7 29 541 45
printing array after sorting : 7 29 45 213 541 3465

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.