Question: Save the following java program into xxxxxH1.java and do as follow: Do not modify constructor and main method (except writing your name in line 92).
Save the following java program into xxxxxH1.java and do as follow:
- Do not modify constructor and main method (except writing your name in line 92).
- Add merge sort and quick sort methods to java e program.
- Modify each sort method to compute no. of comparison and swaps.
- A sample input is as follow:
45 10
84 82 52 80 96 85 75 75 82 87 92 89 57 94 93 92 63 99 87 72
73 56 74 50 84 62 72 55 86 75 74 100 83 60 53 68 89 67 66 65
72 94 73 54 98
1 import java.io.*;
2 import java.util.*;
3
4 // Comp 282
5 // Implementing mergesort and quicksort algorithms
6 // and printing no. of comparisons and swaps.
7 //
8 public class xxxxxH1{
9 // class variables
10 int arr[], barr[], n, k;
11 //varibles to count no. of comparisons and swaps
12 int ncomps, nswaps;
13
14 // class constructor
15 xxxxxH1(){
16 int i;
17 prt.print("\tThis Java program implements mergesort and quicksort algorithms \tand prints no. of comparisons and swaps." +
18 "The program first reads \tn, k and next reads n integers and stores" +
19 "them in array barr[]. \tApplies mergesort and quicksort to the same" +
20 " data and \tprint no. of comparisons and swaps after sorting." +
21 " \t\tTo compile: javac xxxxxH1.java" +
22 " \t\tTo execute: java xxxxxH1 < any data file");
23
24 try{
25 // open input file inf
26 Scanner inf = new Scanner(System.in);
27 // read from input file
28 n = inf.nextInt();//read n, no. of data
29 k = inf.nextInt();//read k, how many per line
30
31 // Its a good practice to print input in program output!
32 prt.printf(" \tn = %3d, k = %4d ", n, k);
33
34 // Allocate space for arr
35 arr = new int[n];
36 barr = new int[n];
37 //loop to read n integers
38 for (i = 0; i < n ; i ++)
39 barr[i] = inf.nextInt();
40 // close input file inf
41 inf.close();
42 } catch (Exception e){ prt.printf(" Ooops! Read Exception: %s", e);}
43
44 } // end constructor
45
46 //use a short word for System.out to save typing
47 PrintStream prt = System.out;
48
49 //
50 // Method to print formatted array, k elements per line
51 private void printarr(){
52 int j;
53 for (j = 0; j < n ; j ++){
54 prt.printf("%4d ", arr[j]);
55 if ((j+1) % k == 0)
56 prt.printf(" \t");
57 } // end for
58 } // end printarr
59
60 //swap arr[j] and arr[k]
61 private void swap(int j, int k){
62 int tmp = arr[j];
63 arr[j] = arr[k];
64 arr[k]= tmp;
65 } // end swap
66
67 // main program
68 public static void main(String args[]) throws Exception{
69 // Create an instance of xxxxxH1 class
70 xxxxxH1 h = new xxxxxH1();
71
72 //copy barr to arr for merge sort,
73 h.arr = h.barr.clone();
74 System.out.printf(" \tInput before merge sort \t");
75 h.printarr();
76 //print no. of comparisons and swaps
h.ncomps = 0; h.nswaps = 0;
77 h.mergesort(0, h.n-1);
78 System.out.printf(" \tComparisons = %d, Swaps = %d", h.ncomps, h.nswaps);
79 System.out.printf(" \tInput after merge sort \t");
80 h.printarr();
81
82 //copy barr to arr, for quick sort
83 h.arr = h.barr.clone();
84 System.out.printf(" \tInput before quick sort \t");
85 h.printarr();
h.ncomps = 0; h.nswaps = 0;
86 h.quicksort(0, h.n-1);
87 System.out.printf(" \tComparisons = %d, Swaps = %d", h.ncomps, h.nswaps);
88 System.out.printf(" \tInput after quick sort \t");
89 h.printarr();
90
91 //MAKE SURE TO WRITE YOUR NAME IN NEXT LINE
92 System.out.printf(" \tAuthor: Gh. Dastghaibyfard Date: " +
93 java.time.LocalDate.now());
94 } // end main
95 } // end class xxxxxH1
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help