The Bubble Sort is named due to how its sorting mechanism moves data items around during its sorting procedure. Heavy items $$sink$$ to the bottom while smaller items $$bubble$$ their way to the top by comparing neighbors and checking for inversions $$ that is$,$ two elements out of order that require a swap. By comparing successive neighbors, we are guaranteed the max element in the last place after the first pass, so we are able to optimize on this search by only inspecting neighbors in the unsorted part of the array $($the unsorted partition$).$ This sort grows the sorted partition by one element $($the largest$)$ each pass and shrinks the unsorted partition accordingly.

$1\mathrm{.}1.$ Download the Sort.java file.

$1\mathrm{.}2.$ Implement the swap method, which swaps two elements of an array. The method should swap the element at indexA with the element at indexB. You can assume that indexA and indexB are within the bounds of the array.

$1\mathrm{.}3.$ Implement the bubbleSort method by following the pseudocode in the lecture slides or your textbook.

$1\mathrm{.}4.$ Test your bubble sort by running the main method.

$1\mathrm{.}5.$ Experiment with optimizing the bubble sort. Can you reduce the inner loop relative to the outer loop? Can you rewrite the outer loop so that it never executes additional times if the list is sorted $$early$?$ For example, the array $[312]$ will need the outer loop to execute only one time, and not three times.

$1\mathrm{.}6.$ Implement another version of the bubble sort method that sorts an array of strings. You will need to write another swap method as well. To compare strings, you can use the compareTo method. This method compares two strings "lexicographically", that is$,$ by dictionary order. If you call stringA.compareTo$($stringB$),$ the result is a negative integer if stringA is less than stringB, a positive integer if stringA is greater than stringB, and zero if the strings are equal.

$1\mathrm{.}7.$ Test your string sort in the main method.$/**$

$*$ This class implements multiple sort algorithms.

$*$

$*$ @author jack Crelencia

$*$ @version $($CSSSKL $143)$

$*/$

public class Sort $\{$

public static final int SIZE $=10$;

public static void main$($String$[]$ args$)\{$

int$[]$ bubbleArray $=$ new int$[$SIZE$]$;

int$[]$ selectionArray $=$ new int$[$SIZE$]$;

int$[]$ insertionArray $=$ new int$[$SIZE$]$;

for $($int i $=0$; i $<$ SIZE; i$++)\{$

bubbleArray$[$i$]=($int$)($Math$.$random$()*52)$;

selectionArray$[$i$]=($int$)($Math$.$random$()*52)$;

insertionArray$[$i$]=($int$)($Math$.$random$()*52)$;

$\}$

System.out.println$("$Array before bubble sort:"$)$;

System.out.println$($Arrays$.$toString$($bubbleArray$))$;

bubbleSort$($bubbleArray$)$;

System.out.println$("$Array after bubble sort:"$)$;

System.out.println$($Arrays$.$toString$($bubbleArray$))$;

System.out.println$()$;

$//$ System.out.println$("$Array before selection sort:"$)$;

$//$ System.out.println$($Arrays$.$toString$($selectionArray$))$;

$//$ selectionSort$($selectionArray$)$;

$//$ System.out.println$("$Array after selection sort:"$)$;

$//$ System.out.println$($Arrays$.$toString$($selectionArray$))$;

$//$ System.out.println$()$;

$//$

$//$ System.out.println$("$Array before insertion sort:"$)$;

$//$ System.out.println$($Arrays$.$toString$($insertionArray$))$;

$//$ insertionSort$($insertionArray$)$;

$//$ System.out.println$("$Array after insertion sort:"$)$;

$//$ System.out.println$($Arrays$.$toString$($insertionArray$))$;

$//$ TODO Test your string sort here

$\}$

$/**$

$*$

$*$ @param numbers

$*/$

public static void bubbleSort$($int$[]$ numbers$)\{$

$//$ Implement your sort, call a helper swap method

$\}$

$/**$

$*$

$*$

$*$ @param numbers

$*$ @param indexA

$*$ @param indexB

$*/$

public static void swap$($int$[]$ numbers, int indexA, int indexB$)\{$

$//$ swap the elements at indexA and indexB

$\}$

$//$ selection sort for ints

public static void selectionSort$($int$[]$ numbers$)\{$

$//$ Implement your sort, call swapSelection$($int$[]$ intList, int i$,$ in nextMin$)$

$\}$

public static int findSmallest$($int$[]$ arr, int begin, int end$)\{$

int minIndex $=$ begin;

int minValue $=$ arr$[$begin$]$;

for $($int i $=$ begin $+1$; i $<$ end; i$++)\{$

if $($arr$[$i$]<$ minValue$)\{$

minIndex $=$ i;

minValue $=$ arr$[$i$]$;

$\}$

$\}$

return minIndex;

$\}$

$/**$

$*$

$*$ @param numbers

$*/$

public static void insertionSort$($int$[]$ numbers$)\{$

$//$ Implement your insertion sort

$\}$

$\}$