Question

In: Computer Science

Create a program named MergeSort.java then copy the following code to your program: public static void...

  1. Create a program named MergeSort.java then copy the following code to your program:
    • public static void mergeSort(int[] arr){
         mergeSortRec(arr, 0, arr.length-1);
      }
      private static void mergeSortRec(int[] arr, int first, int last){
         if(first<last){
          int mid=(first+last)/2;
      mergeSortRec(arr, first, mid);
          mergeSortRec(arr, mid+1,last);
          merge(arr, first, mid, mid+1, last);
         }
      }
      private static void merge(int[] arr, int leftFirst,
         int leftLast, int rightFirst, int rightLast){
         int[] aux=new int[arr.length];
         //extra space, this is downside of this algorithm
         int index=leftFirst;
         int saveFirst=leftFirst;
         while(leftFirst<=leftLast && rightFirst <=rightLast){
      if(arr[leftFirst]<=arr[rightFirst]){
         aux[index++]=arr[leftFirst++];
          }else{
         aux[index++]=arr[rightFirst++];
          }
         }
         while(leftFirst<=leftLast){
          aux[index++]=arr[leftFirst++];
         }
         while(rightFirst<=rightLast)
          aux[index++]=arr[rightFirst++];
         for(index=saveFirst; index<=rightLast; index++)
          arr[index]=aux[index];
      }
  2. Write a main method that accepts three numbers N, A, B (assume A<B) from the command argument list, then use the number N to create an N-element int array.
  3. Assign random numbers between [A, B] to each of the N elements of the array.
  4. Call mergeSort method to sort the array.
  5. Write instructions to record the time spent on sorting.
  6. (Optional) you may write code to verify the array was sorted successfully.
  7. Once completed, test your program with different numbers N, A, B and screenshot your result. Your result should include the number of elements and sorting time.
  8. Please include the following in the Word document you created for the assignment for the final submission:  
    • Copy/paste your completed code in MergeSort.java
    • Insert at least one screenshot of the running output in #7 above
    • Answer this question: What is the average Big O for this sort?

Solutions

Expert Solution

Complete code in java:-

import java.util.Random;
import java.util.Scanner;
import java.io.*;

class MergeSort {

// These are methods provided by you for sorting the input array
// Below method is driver method.
public static void mergeSort(int[] arr){
mergeSortRec(arr, 0, arr.length-1);
}

// This is the main function to sort the array.
private static void mergeSortRec(int[] arr, int first, int last){
if(first<last){

// Partition the array into two equal halves
int mid=(first+last)/2;

// Calling this function recurrsively for both the halves.
mergeSortRec(arr, first, mid);
mergeSortRec(arr, mid+1,last);

// Finally merging the two sorted halves.
merge(arr, first, mid, mid+1, last);
}
}

// This function will merge the 2 sorted halves and make a sorted array.
private static void merge(int[] arr, int leftFirst,
int leftLast, int rightFirst, int rightLast){
int[] aux=new int[arr.length];
//extra space, this is downside of this algorithm
int index=leftFirst;
int saveFirst=leftFirst;

// From here, this code is merging 2 sorted halves into one.
while(leftFirst<=leftLast && rightFirst <=rightLast){
if(arr[leftFirst]<=arr[rightFirst]){
aux[index++]=arr[leftFirst++];
}else{
aux[index++]=arr[rightFirst++];
}
}

while(leftFirst<=leftLast){
aux[index++]=arr[leftFirst++];
}

while(rightFirst<=rightLast)
aux[index++]=arr[rightFirst++];
for(index=saveFirst; index<=rightLast; index++)
arr[index]=aux[index];
}

// Main method
public static void main(String ... args) {

// Creating object for random number generation.
Random rand = new Random();

// Creating Scanner object for taking user input
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a = sc.nextInt();
int b = sc.nextInt();

// Creating array of size 'n'.
int arr[] = new int[n];

// Storing numbers into array in range 'a'-'b'
for(int i = 0; i < n; i++) {
arr[i] = rand.nextInt((b-a)+1)+a;
}

// Here we measuring time before starting mergeSort method.
long start = System.currentTimeMillis();
mergeSort(arr);

// Again measuring time before starting mergeSort method.
long end = System.currentTimeMillis();

// Priting desired output.
System.out.println("Time taken to sort "+n+ " numbers : " + (end - start) + "ms");
}
}

Screenshot of output:-

Mege sort uses divide and conquer technique, every time it divides array into 2 almost equal halves and merge this halves into one sorted subarray. Its average case time complexity is O(n*log(n)).


Related Solutions

Create a new Java file, containing this code public class DataStatsUser { public static void main...
Create a new Java file, containing this code public class DataStatsUser { public static void main (String[] args) { DataStats d = new DataStats(6); d.append(1.1); d.append(2.1); d.append(3.1); System.out.println("final so far is: " + d.mean()); d.append(4.1); d.append(5.1); d.append(6.1); System.out.println("final mean is: " + d.mean()); } } This code depends on a class called DataStats, with the following API: public class DataStats { public DataStats(int N) { } // set up an array (to accept up to N doubles) and other member...
Task 2/2: Java program Based upon the following code: public class Main {   public static void...
Task 2/2: Java program Based upon the following code: public class Main {   public static void main( String[] args ) {     String alphabet = "ABCDEFGHIJKLMNMLKJIHGFEDCBA";     for( <TODO> ; <TODO> ; <TODO> ) {       <TODO>;     } // Closing for loop   } // Closing main() } // Closing class main() Write an appropriate loop definition and in-loop behavior to determine if the alphabet string is a palindrome or not. A palindrome is defined as a string (or more generally, a token) which...
CODE: C# using System; public static class Lab6 { public static void Main() { // declare...
CODE: C# using System; public static class Lab6 { public static void Main() { // declare variables int hrsWrked; double ratePay, taxRate, grossPay, netPay=0; string lastName; // enter the employee's last name Console.Write("Enter the last name of the employee => "); lastName = Console.ReadLine(); // enter (and validate) the number of hours worked (positive number) do { Console.Write("Enter the number of hours worked (> 0) => "); hrsWrked = Convert.ToInt32(Console.ReadLine()); } while (hrsWrked < 0); // enter (and validate) the...
public class GreeterTest {    public static void main(String[] args)    { // create an object...
public class GreeterTest {    public static void main(String[] args)    { // create an object for Greeter class Greeter greeter = new Greeter("Jack"); // create two variables Greeter var1 = greeter; Greeter var2 = greeter; // call the sayHello method on the first Greeter variable String res1 = var1.sayHello(); System.out.println("The first reference " + res1); // Call the setName method on the secod Grreter variable var2.setName("Mike"); String res2 = var2.sayHello(); System.out.println("The second reference " + res2);    } }...
Consider the following code: public class Example { public static void doOp(Op op) { boolean result...
Consider the following code: public class Example { public static void doOp(Op op) { boolean result = op.operation(true, false); System.out.println(result); } public static void main(String[] args) { doOp(new AndOperation()); doOp(new OrOperation()); } } main's output: false true Define any interfaces and/or classes necessary to make this output happen. Multiple answers are possible. You may not modify any of the code in Example.
Consider the following code: import java.util.Scanner; public class Main {    public static void main(String[] args)...
Consider the following code: import java.util.Scanner; public class Main {    public static void main(String[] args) {    Scanner in = new Scanner(System.in); String input = ""; System.out.println("Enter the first number: ");    input = in.nextLine(); int a = 0; int b = 0;    a = Integer.parseInt(input);    System.out.println("Enter the second number: "); input = in.nextLine();    b = Integer.parseInt(input);    int result = 0; result = a/b;    System.out.println("a/b : " + result);    } Copy the code...
in java. using the following template as a method, public static void shellSort(int[] array) { create...
in java. using the following template as a method, public static void shellSort(int[] array) { create a program that counts the number of comparisons and swaps of the sorting method does using int array1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // Best Case Test int array2[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; // Worst Case Test int array3[] = {10, 4, 8, 2, 6, 1, 9, 3, 7, 5}; //...
DESCRIBE WHAT THE FOLLOWING JAVA CODE DOES: public class Main{ public static void main(String[] args) {...
DESCRIBE WHAT THE FOLLOWING JAVA CODE DOES: public class Main{ public static void main(String[] args) { new MyFrame(); } } import javax.swing.*; public class MyFrame extends JFrame{ MyPanel panel; MyFrame(){ panel = new MyPanel(); this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); this.add(panel); this.pack(); this.setLocationRelativeTo(null); this.setVisible(true); } } import java.awt.*; import javax.swing.*; public class MyPanel extends JPanel{ //Image image; MyPanel(){ //image = new ImageIcon("sky.png").getImage(); this.setPreferredSize(new Dimension(500,500)); } public void paint(Graphics g) { Graphics2D g2D = (Graphics2D) g; //g2D.drawImage(image, 0, 0, null); g2D.setPaint(Color.blue); g2D.setStroke(new BasicStroke(5)); g2D.drawLine(0, 0, 500,...
Analyze the following code: public class Test {   public static void main(String[] args) { xMethod(5, 500L);...
Analyze the following code: public class Test {   public static void main(String[] args) { xMethod(5, 500L);   }   public static void xMethod(int n, long l) {     System.out.println("int, long");   }   public static void xMethod(long n, long l) {     System.out.println("long, long");   } } Group of answer choices The program prints 2 lines: int, long long, long The program contains a compile error because Java can't tell which method to invoke. The program prints long, long The program prints int, long
Correct the code: import java.util.Scanner; public class Ch7_PrExercise5 { public static void main(String[] args) {   ...
Correct the code: import java.util.Scanner; public class Ch7_PrExercise5 { public static void main(String[] args) {    Scanner console = new Scanner(System.in);    double radius; double height; System.out.println("This program can calculate "+ "the area of a rectangle, the area "+ "of a circle, or volume of a cylinder."); System.out.println("To run the program enter: "); System.out.println("1: To find the area of rectangle."); System.out.println("2: To find the area of a circle."); System.out.println("3: To find the volume of a cylinder."); System.out.println("-1: To terminate the...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT