Write a java program to read in a set of numbers and perform a “MergeSort” to ar

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.

Down below is some code that can be used.

some of the code is written down below.

public int runCount(mergeSort Q)

{

         int count=1;

         int prior=-9999;

         for(int i=0; i

         {

               if(Q.front()

               {

                     count++;

                     prior=Q.front();

                     Q.insert(Q.front());

                     Q.remove();

               }

         }

         return count;

   }

Explanation / Answer

Java Program:

import java.util.Scanner;

import java.util.LinkedList;

import java.util.Queue;

class Main

{

static void merge(int data[], int left, int middle, int right, Queue<Integer> queue)

{

int size_of_array1 = middle - left + 1;

int size_of_array2 = right - middle;

int left_array[] = new int [size_of_array1];

int right_array[] = new int [size_of_array2];

for (int i=0; i<size_of_array1; ++i)

left_array[i] = data[left + i];

for (int j=0; j<size_of_array2; ++j)

right_array[j] = data[middle + 1+ j];

int i = 0, j = 0;

int k = left;

while (i < size_of_array1 && j < size_of_array2)

{

if (left_array[i] <= right_array[j])

{

data[k] = left_array[i];

i++;

}

else

{

data[k] = right_array[j];

j++;

}

k++;

}

while (i < size_of_array1)

{

data[k] = left_array[i];

i++;

k++;

}

while (j < size_of_array2)

{

data[k] = right_array[j];

j++;

k++;

}

}

static void sort(int data[], int left, int right, Queue<Integer> queue)

{

if (left < right)

{

int middle = (left+right)/2;

sort(data, left, middle, queue);

sort(data , middle+1, right, queue);

merge(data, left, middle, right, queue);

}

}

static void ascending_runs(int data[], int n, Queue<Integer> queue)

{

int i;

boolean flag = false;

for (i=1; i<n; ++i)

{

if(data[i-1] <= data[i])

{

flag =true;

queue.add(data[i-1]);

}

else if(data[i-1] > data[i] && flag == true)

{

flag =false;

queue.add(data[i-1]);

queue.add(-9999); //violation in ascending run

}

}

if(data[i-2] <= data[i-1])

queue.add(data[i-1]);

}

public static void main(String args[])

{

int i,n,val,queue_size;

Queue<Integer> queue = new LinkedList<>();

System.out.print("Enter number of element: ");

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

int[] data=new int[100];

for(i=0;i<n;i++)

{

System.out.print("Enter "+i+"'th element: ");

data[i] = sc.nextInt();

}

ascending_runs(data, n, queue);

queue_size = queue.size();

System.out.println(" Printing all ascending runs...");

for (i=0; i<queue_size; ++i)

{

val = queue.remove();

if(val != -9999)

System.out.print(val + " ");

else

System.out.print(" ");

}

sort(data, 0, n-1,queue);

System.out.print(" Array after sorting: ");

for (i=0; i<n; ++i)

System.out.print(data[i] + " ");

System.out.print(" ");

}

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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