b) Add bubble sort, insertion sort and selection sort methods to above program. c) Modify each sort method that computes and prints no. of comparison and swaps

after sorting. Add the following statement at the end of each sort method:

prt.printf(" \tComparisons = %d, Swaps = %d", ncomps, nswaps);

d) A sample input can be as follow: 50 15

200 184 125 175 151 129 106 152 163 168 106 166 105 162 107 171 740 176 501 194 174 115 108 445 154 139 140 150 193 128 159 157 186 315 190 142 191 108 151 113 148 164 150 171 144 176 191 114 124 171

1. 1 import java.io.*;

2. 2 import java.util.*;

3

4. 5 // Implementing bubble, insertion and selection sort algorithms

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

6. 7 // Author: G. Dastghaiby Fard

8 public class xxxxxH2{

9. 9 // class variables

10. 10 int arr[], barr[], n, k;

11. 11 //varibles to count no. of comparisons and swaps

12. 12 int nswap, ncomp;

13

14. 14 //use a short word for System.out to save typing

15. 15 PrintStream prt = System.out;

16

17

18 19 20

// class constructor

xxxxxH2 (){ int i; prt.print("\tThis Java program implements bubble, insertion and selection

sort \t" +

21. 21 "algorithms and prints no. of comparisons and swaps. \t" +

22. 22 "The program first reads n, k and next reads n integers and stores \t" +

23. 23 "them in array barr[]. \tApplies bubble, insertion and selection sort to the

same \t" + 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

"data and print no. of comparisons and swaps after sorting." + " \t\tTo compile: javac xxxxxH2.java" +

" \t\tTo execute: java xxxxxH2 < any data file");

try{ // open input file inf Scanner inf = new Scanner(System.in); // read from input file n = inf.nextInt();//read n, no. of data k = inf.nextInt();//read k, how many per line

// Its a good practice to print input in program output! prt.printf(" \tn = %3d, k = %4d ", n, k);

// Allocate space for arr

arr = new int[n]; barr = new int[n]; //loop to read n integers for (i = 0; i < n ; i ++)

barr[i] = inf.nextInt(); // close input file inf inf.close();

} catch (Exception e){ prt.printf(" Ooops! Read Exception: %s", e);}

} // end constructor

//Method to print formatted array, //k elements per line

52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88

private void printarr(){ int j;

for (j = 0; j < n ; j ++){ prt.printf("%4d ", arr[j]); if ((j+1) % k == 0)

prt.printf(" \t"); } // end for

} // end printarr

//swap arr[j] and arr[k] private void swap(int j, int k){

int tmp = arr[j]; arr[j] = arr[k]; arr[k]= tmp;

} // end swap

// main program public static void main(String args[]) throws Exception{

// Create an instance of xxxxxH2 class xxxxxH2 h = new xxxxxH2();

//copy barr to arr for bubble sort, h.arr = h.barr.clone(); System.out.printf(" \tInput before bubble sort \t"); h.printarr(); h.bubble(); System.out.printf(" \tInput after bubble sort \t"); h.printarr();

//copy barr to arr for insertion sort, h.arr = h.barr.clone(); System.out.printf(" \tInput before insertion sort \t"); h.printarr(); h.insertion(); System.out.printf(" \tInput after insertion sort \t"); h.printarr();