java

1. The Shell sort (invented by Dr. Donald Shell) is a variation of the bubble/exchange sort. Instead of comparing adjacent values, the Shell sort adapts the partitioning concept from the binary search to determine a "gap" across which values are compared before any swap takes place. In the first pass, the gap is half the size of the array. For each subsequent pass, the gap size is cut in half. For the final pass(es), the gap size is 1, so it would be the same as a bubble sort. The passes continue until no swaps occur. Below is the same set of values as per the bubble sort example in Chapter 18 (p. 667), showing the first pass of the Shell sort: 9 6 8 12 3 1 7 -- size of array is 7, so gap would be 3 9 6 8 12 3 17 9 6 8 12 3 1 7 9 3 8 12 6 17 A- 931 12 687 -- 9 and 12 are already in order, so no swap - 6 and 3 are not in order, so swap -- 8 and 1 are not in order, so swap -- 12 and 7 are not in order, so swap - end of pass 1 9 3 8 7 6 1 12 The pseudo-code for the Shell sort is as follows: gap = size / 2 do until gap num(a + gap) swap num(a) with numa + gap) awapflag = true ande Way end-if end-for end-do gap = gap / 2 end-do Modify Sorting.java to include a shellsort method that implements the above algorithm. Include an output of the array any time a swap occurs to demonstrate that your code works correctly. For the driver, create an Integer array using an initializer list to reproduce the above example and two additional random sets of 10 and 20 integers. 2. The bubble sort algorithm shown in Chapter 18 is less efficient than it could be. If a pass is made through the list without exchanging any elements, the list is sorted and there is no reason to continue. Create a copy of the bubbleSort method called bubblesort2 that implements this algorithm so that is will stop as soon as it recognizes that the list is sorted. Do not use a break statement! Include outputs of the array for both sorts for each pass through the array so you can demonstrate that the code is working correctly. The driver should test both methods with a random set of 10 integers and an already sorted set of 10 integers. Hint: You have to introduce a swapflag that is set true if a swap occurs on a given pass. Replace the outer "for loop" with a "while loop" that tests the swapflag and takes care of "index counting" within the loop. Hint: Remember that arrays are passed by reference in Java. Use Arrays.copyof) or a similar method to test each sort method on the exact same data content in separate arrays