In this program, you will implement an insertion sort on an ArrayList of Strings. However, you use the approach described in the notes.

First, write the switchValues method

public static void switchValues( ArrayList a, int n1, int n2 )

Precondition: 0 <= n1 < a.size

0 <= n2 < a.size

Postcondition: The ArrayList is unchanged except that the string at index n1 is now at index n2; and the string that was at index n2 is now at index n1

Second, write the insertAbove method.

public static void insertAbove( ArrayList a, int n )

Precondition: 1 <= n1 < a.size

The array list is sorted in ascending from in the indices [0, n-1]

Postcondition: The array list is sorted in ascending from in the indices [0, n] and the other elements of the list are not changed.

Third, write the insertionSort method.

public static void insertionSort( ArrayList a ){

Sort the list using the insertion sort algorithm

It should be two lines long and one line should call the insertAbove method

Main.Java

import java.util.ArrayList;

public class Main { public static void main(String[] args) { ArrayList a = new ArrayList<>(); a.add( "X" ); a.add( "B" ); a.add( "O" ); a.add( "H" ); a.add( "P" ); a.add( "E" ); insertionSort( a ); System.out.println( a); // [B, E, H, O, P, X] System.out.println("************"); ArrayList b = new ArrayList<>(); b.add( "mouse" ); b.add( "house" ); b.add( "rat" ); b.add( "ant" ); b.add( "animal" ); b.add( "kangaroo" ); b.add( "tiger" ); b.add( "aunt" ); insertionSort( b ); System.out.println( b ); // [animal, ant, aunt, house, kangaroo, mouse, rat, tiger] } public static void switchValues( ArrayList a, int n1, int n2 ){ /* Precondition: 0 <= n1 < a.size 0 <= n2 < a.size Postcondition: The ArrayList is unchanged except that the string at index n1 is now at index n2; and the string that was at index n2 is now at index n1 */

} public static void insertAbove( ArrayList a, int n ){ /* Precondition: 1 <= n1 < a.size Precondition: The array list is sorted in ascending from in the indices [0, n-1] Postcondition: The array list is sorted in ascending from in the indices [0, n] and the other elements of the list are not changed. This method should call the switchValues method. */

} public static void insertionSort( ArrayList a ){ // Sort the list using the insertion sort algorithm // It should be two lines long and one line should call the insertAbove method

} }