Note: Problem 4.1, 4.2, no coding needed. And problem 4.3 is programming required.

4.1 Given the following array of 7 elements, trace the bubble sort algorithm on iteration of outer loop at a time. Assume the array is to be sorted in ascending order.

14 7 9 28 5 3 11

The answer of the first iteration has been given:

The 1th iteration: 7 9 14 5 3 11 28

4.2 Given the following array of 7 elements, trace the selection sort algorithm on iteration of outer loop at a time. Assume the array is to be sorted in ascending order.

14 7 9 28 5 3 11

The answer of the first iteration has been given:

The 1th iteration: 3 7 9 28 5 14 11

4.3 (Programming Projects 3.1 in textbook) In the BubbleSortApp.java program attached, the in index always goes from left to right, finding the largest item and carrying it toward out on the right. Modify the bubbleSort() method so that its bidirectional. This means the in index will first carry the largest item from left to right as before, but when it reaches out, it will reverse and carry the smallest item from right to left. Youll need two outer indexes, one on the right (the old out) and another on the left.

// bubbleSort.java // demonstrates bubble sort // to run this program: C>java BubbleSortApp //////////////////////////////////////////////////////////////// class ArrayBub { private long[] a; // ref to array a private int nElems; // number of data items //-------------------------------------------------------------- public ArrayBub(int max) // constructor { a = new long[max]; // create the array nElems = 0; // no items yet } //-------------------------------------------------------------- public void insert(long value) // put element into array { a[nElems] = value; // insert it nElems++; // increment size } //-------------------------------------------------------------- public void display() // displays array contents { for(int j=0; j0; out--) // outer loop (backward) for(in=0; in a[in+1] ) // out of order? swap(in, in+1); // swap them } // end bubbleSort() //-------------------------------------------------------------- private void swap(int one, int two) { long temp = a[one]; a[one] = a[two]; a[two] = temp; } //-------------------------------------------------------------- } // end class ArrayBub //////////////////////////////////////////////////////////////// public class BubbleSortApp { public static void main(String[] args) { int maxSize = 3; // array size ArrayBub arr; // reference to array arr = new ArrayBub(maxSize); // create the array arr.insert(77); // insert 10 items arr.insert(99); arr.insert(44); arr.insert(55); arr.insert(22); arr.insert(88); arr.insert(11); arr.insert(00); arr.insert(66); arr.insert(33); arr.display(); // display items arr.bubbleSort(); // bubble sort them arr.display(); // display them again } // end main() } // end class BubbleSortApp ////////////////////////////////////////////////////////////////