AP Computer Science Exam Question

Implement the insertion sort algorithm to sort an integer array named arr in ascending order.

Define the following method in the InsertionSort class:

public static void insertionSort(int[] arr)

Your implementation should rearrange the elements in the arr array in ascending order using the insertion sort algorithm.

Answer

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }
}

The given solution implements the insertion sort algorithm in the InsertionSort class. The insertionSort method takes an integer array arr as input and sorts it in ascending order using the insertion sort algorithm.

The algorithm works by maintaining a sorted subarray to the left of the current element. Starting from the second element (index 1) of the array, the algorithm iterates over the remaining unsorted elements. For each element, it compares it with the elements in the sorted subarray and shifts them to the right until the correct position is found to insert the current element.

Starting from i = 1, the algorithm follows these steps:

1. Assign the value of arr[i] to the variable key. This value will be inserted into the correct position in the sorted subarray.

2. Initialize j as i - 1, representing the last index of the sorted subarray.

3. Compare key with arr[j]. If arr[j] is greater than key, shift arr[j] to the right by assigning arr[j + 1] the value of arr[j] and decrement j.

4. Repeat step 3 until either j becomes less than 0 or arr[j] is not greater than key.

5. Assign key to arr[j + 1], inserting it in the correct position in the sorted subarray.

6. Increment i and repeat steps 1-5 until all elements have been considered.

After the insertionSort method completes, the elements in the arr array will be sorted in ascending order.

The time complexity of the insertion sort algorithm is O(n^2) in the worst case, where n is the number of elements in the array.