Write a java program to read in a set of numbers and perform a “MergeSort” to ar
ID: 3709975 • Letter: W
Question
Write a java program to read in a set of numbers and perform a “MergeSort” to arrange the numbers in ascending order. Your program is expected to use queues to keep track of the ascending “runs” in the numbers, which are portions that are already in order.
Remember: You must create a number queue to do mergeSort not arrays. It has to be Queues!
Can you fix this java code. I can't get runCount to work in test.
import java.util.Random;
public class mergeSort {
public static final int MAXSIZE = 100;
public int getQsize() {
return (MAXSIZE + lastLoc - firstLoc) % MAXSIZE;
}
public boolean fullCheck() {
return (getQsize() == MAXSIZE - 1);
}
public boolean emptyCheck() {
return (getQsize() == 0);
}
public int insert(int val) {
if (fullCheck())
return -1;
else {
numArray[lastLoc] = val;
lastLoc = (lastLoc + 1) % MAXSIZE;
return 0;
}
}
public int front() {
return numArray[firstLoc];
}
public void remove() {
if (!emptyCheck())
firstLoc = (firstLoc + 1) % MAXSIZE;
}
private int firstLoc = 0;
private int lastLoc = 0;
private int[] numArray = new int[MAXSIZE];
public int getFirstLoc() {
return firstLoc;
}
public void setFirstLoc(int firstLoc) {
this.firstLoc = firstLoc;
}
public int getLastLoc() {
return lastLoc;
}
public void setLastLoc(int lastLoc) {
this.lastLoc = lastLoc;
}
public int[] getNumArray() {
return numArray;
}
public void setNumArray(int[] numArray) {
this.numArray = numArray;
}
public void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
//Create temp arrays /
int L[] = new int[n1];
int R[] = new int[n2];
// Copy data to temp arrays /
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while(i<n1) {
arr[k]=L[i];
i++;
k++;
}
}
void sort(int arr[], int l, int r)
{
if(l<r) {
int m=(int)Math.ceil((l+r)/2);
sort(arr,l,m);
sort(arr,m+1,r);
merge(arr,l,m,r);
}
}
public void printArray(int arr[], int i, int n) {
for(i=0;i<n;i++)
System.out.print(arr[i]+" ");
System.out.println();
}
public int runCount(mergeSort Q)
{
int count=1;
int prior=-9999;
for(int i=0;i<Q.getQsize();i++);
{
if(Q.front()<prior)
{
count++;
prior=Q.front();
Q.insert(Q.front());
Q.remove();
}
}
return count;
}
}
import java.util.Scanner;
import java.util.Random;
public class Tester {
public static void main(String[] args)
{
int val;
mergeSort queue=new mergeSort();
for(int i=0; i<10; i++)
queue.insert(new Random().nextInt(100)+1);
System.out.println("initial array");
queue.printArray(queue.getNumArray(), queue.getFirstLoc(), queue.getLastLoc());
mergeSort sort=new mergeSort();
sort.sort(queue.getNumArray(), queue.getFirstLoc(), queue.getLastLoc()-1);
System.out.println("sorted array");
queue.printArray(queue.getNumArray(), queue.getFirstLoc(), queue.getLastLoc());
System.out.println("printing all ascending runs...");
import java.util.Random;
public class mergeSort {
public static final int MAXSIZE = 100;
public int getQsize() {
return (MAXSIZE + lastLoc - firstLoc) % MAXSIZE;
}
public boolean fullCheck() {
return (getQsize() == MAXSIZE - 1);
}
public boolean emptyCheck() {
return (getQsize() == 0);
}
public int insert(int val) {
if (fullCheck())
return -1;
else {
numArray[lastLoc] = val;
lastLoc = (lastLoc + 1) % MAXSIZE;
return 0;
}
}
public int front() {
return numArray[firstLoc];
}
public void remove() {
if (!emptyCheck())
firstLoc = (firstLoc + 1) % MAXSIZE;
}
private int firstLoc = 0;
private int lastLoc = 0;
private int[] numArray = new int[MAXSIZE];
public int getFirstLoc() {
return firstLoc;
}
public void setFirstLoc(int firstLoc) {
this.firstLoc = firstLoc;
}
public int getLastLoc() {
return lastLoc;
}
public void setLastLoc(int lastLoc) {
this.lastLoc = lastLoc;
}
public int[] getNumArray() {
return numArray;
}
public void setNumArray(int[] numArray) {
this.numArray = numArray;
}
public void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
//Create temp arrays /
int L[] = new int[n1];
int R[] = new int[n2];
// Copy data to temp arrays /
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while(i<n1) {
arr[k]=L[i];
i++;
k++;
}
}
void sort(int arr[], int l, int r)
{
if(l<r) {
int m=(int)Math.ceil((l+r)/2);
sort(arr,l,m);
sort(arr,m+1,r);
merge(arr,l,m,r);
}
}
public void printArray(int arr[], int i, int n) {
for(i=0;i<n;i++)
System.out.print(arr[i]+" ");
System.out.println();
}
public int runCount(mergeSort Q)
{
int count=1;
int prior=-9999;
for(int i=0;i<Q.getQsize();i++);
{
if(Q.front()<prior)
{
count++;
prior=Q.front();
Q.insert(Q.front());
Q.remove();
}
}
return count;
}
}
Explanation / Answer
code : public class NumberQueue { public static final int MAXSIZE = 100; public int getQsize() { return (MAXSIZE + lastLoc - firstLoc) % MAXSIZE; } public boolean fullCheck() { return (getQsize() == MAXSIZE - 1); } public boolean emptyCheck() { return (getQsize() == 0); } public int insert(int val) { if (fullCheck()) return -1; else { numArray[lastLoc] = val; lastLoc = (lastLoc + 1) % MAXSIZE; return 0; } } public int front() { return numArray[firstLoc]; } public void remove() { if (!emptyCheck()) firstLoc = (firstLoc + 1) % MAXSIZE; } private int firstLoc = 0; private int lastLoc = 0; private int[] numArray = new int[MAXSIZE]; public int getFirstLoc() { return firstLoc; } public void setFirstLoc(int firstLoc) { this.firstLoc = firstLoc; } public int getLastLoc() { return lastLoc; } public void setLastLoc(int lastLoc) { this.lastLoc = lastLoc; } public int[] getNumArray() { return numArray; } public void setNumArray(int[] numArray) { this.numArray = numArray; } } import java.util.Random; public class NumberQueueSort { void merge(int arr[], int l, int m, int r) { int n1 = m - l + 1; int n2 = r - m; int L[] = new int[n1]; int R[] = new int[n2]; for (int i = 0; iRelated Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.