Use the following code provided. Write two method name mergesort and quicksort to fit the following code.

1. Do not modify constructor and main method (except writing your name in line 92).
2. Add merge sort and quick sort methods to java e program.
3. Modify each sort method to compute no. of comparison and swaps.
4. 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

NOTE: Homeworks will not be graded if:

Your complete homework is not in a SINGLE xxxxxH1.java file, where xxxxx is at most

the 1^st first 5 characters of your last name and H1 is the Homework number.

Using package or have compile error.

Does not compile or execute at the command prompt.

It does not read input, from any input file.

-----------------------------------------------------------------------------------------------------------------------------------------------------------

import java.io.*;

2 import java.util.*;

3

4 // CSUN COMP 282 Sp 21, Homework-1

5 // Implementing mergesort and quicksort algorithms

6 // and printing no. of comparisons and swaps.

7 // Author: G. Dastghaiby Fard

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