Java Assignment:

Setup:

A template code, "Lab 10", has been given below under subheader "Template Code". Modify this code to complete the assignment. Make sure the output is the same as given below under "Sample Output"!

Instructions:

A base file, Lab10.java, is included. You may use this as your basis for the assignment.

You will note that there is an array

public static int[][] deepCopy(int[][] arr) 

That is, it will accept a two-dimensional array (of any size, including ragged ones) and return a new array of the same size and with the same values. For example, if I pass in an array such as:

{ {1, 2, 3} {4, 5, 6, 7, 8, 9, 10}, {-1} } 

It will return a new array of the same sizes and with the same values. It should NOT return a reference to the same array, or to any of the subarrays! The arrays must be entirely separate.

Then, your program should make a copy of the array a1 and put it in a different variable, a2.

You will note that the original array has five sub-arrays. Each of these sub-arrays should be sorted, with the ones in a1 being sorted by Bubble Sort (described below) and the ones in a2 by Selection Sort. These should be two separate methods. Each of these methods should return an int representing the number of times a swap occurred when sorting one particular sub-array.

After sorting each sub-array through both bubble and selection sorts, display the now-sorted array and number of swaps necessary. For example, for the first sub-array for a1 and a2, your output should look like this:

Bubble sort: [ 3, 4, 5, 6, 8, 9 ] Swaps = 13 Selection sort: [ 3, 4, 5, 6, 8, 9 ] Swaps = 3 

Bubble Sort is a similar kind of sort to Selection Sort, in that it involves swapping values. Selection Sort spends each iteration looking through the rest of the values to see what belongs in position 0, 1, 2, etc., and swapping them. Bubble Sort, however, will only look at the two elements right next to each other. If the "left" value (e.g., position 4) is greater than the "right" value (e.g., position 5), then the sort will swap them. If not, it leaves them alone.

At the end of an iteration, the Bubble Sort will most likely not be done. Instead, it will have to start back at the beginning of the array and once again look through all the values to see if any need to be swapped. The Bubble Sort will keep going through the list until there have been no swaps during an iteration, at which point all of the values are in the correct order.

Looking through the output below, notice how smaller values slowly "bubble" to the beginning of the array, and larger values slowly "sink" to the end.

Sample Output:

Iteration 0 [ 8, 9, 5, 6, 4, 3 ] Swapping position 1 (Value: 9) and 2 (Value: 5) [ 8, 5, 9, 6, 4, 3 ] Swapping position 2 (Value: 9) and 3 (Value: 6) [ 8, 5, 6, 9, 4, 3 ] Swapping position 3 (Value: 9) and 4 (Value: 4) [ 8, 5, 6, 4, 9, 3 ] Swapping position 4 (Value: 9) and 5 (Value: 3) Iteration 1 [ 8, 5, 6, 4, 3, 9 ] Swapping position 0 (Value: 8) and 1 (Value: 5) [ 5, 8, 6, 4, 3, 9 ] Swapping position 1 (Value: 8) and 2 (Value: 6) [ 5, 6, 8, 4, 3, 9 ] Swapping position 2 (Value: 8) and 3 (Value: 4) [ 5, 6, 4, 8, 3, 9 ] Swapping position 3 (Value: 8) and 4 (Value: 3) Iteration 2 [ 5, 6, 4, 3, 8, 9 ] Swapping position 1 (Value: 6) and 2 (Value: 4) [ 5, 4, 6, 3, 8, 9 ] Swapping position 2 (Value: 6) and 3 (Value: 3) Iteration 3 [ 5, 4, 3, 6, 8, 9 ] Swapping position 0 (Value: 5) and 1 (Value: 4) [ 4, 5, 3, 6, 8, 9 ] Swapping position 1 (Value: 5) and 2 (Value: 3) Iteration 4 [ 4, 3, 5, 6, 8, 9 ] Swapping position 0 (Value: 4) and 1 (Value: 3) Iteration 5 [ 3, 4, 5, 6, 8, 9 ] Swaps = 13 

Note the final iteration (5) sees no swaps done. This means that the array has already been sorted - there is nothing left to do.

While Bubble Sort is rarely used due to its (lack of) speed, it is used occasionally in graphics programming since it can tell you very quickly and with a minimum of computing power whether or not a list is already sorted.

Template Code:

*Note that you will have to change some of already-existing code in order to complete this lab*

import java.util.*; public class Lab10 { /** * Helper method for printing out arrays. * @param int[] arr Array of integers to print */ public static void printArray(int[] arr) { System.out.print("[ "); for (int j=0; j < (arr.length - 1); j++) { System.out.print(arr[j] + ", "); } if (arr.length > 0) { System.out.print(arr[arr.length - 1]); } System.out.println(" ]"); } /** * Swap two elements in an array * @param int[] arr - the array * @param int index1 - the index of first element to swap * @param int index2 - the index of the second element to swap */ public static void swap(int[] arr, int index1, int index2) { if (index1 == index2) { // Do nothing! } else { int tmp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = tmp; } } /** * Sort an array in ascending order using the Selection Sort algorithm * @param int[] arr - the array */ public static void selectionSort(int[] arr) { if (arr.length < 2) { return; } int minIndex = 0; int minVal = 0; for (int j = 0; j < (arr.length-1); j++) { printArray(arr); minIndex = j; minVal = arr[j]; for(int k = j + 1; k < arr.length; k++) { if (arr[k] < minVal) { minVal = arr[k]; minIndex = k; } } swap(arr, j, minIndex); } } public static void main(String[] args) { int[][] a1 = { {8, 9, 5, 6, 4, 3}, {9, 0, 14, 13, 10, 8, 2, 1, 17, 18, 19, 201, 220, 235, 2}, {100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 1100, 1200 }, {22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 1}, {20, 18, 13, 12, 11, 9, 6, 5, 4, 3, 2, 1, -87, -900, -9, -909, -911, -80, -44, -32, -1000} }; } }