AP Computer Science Exam Question

Consider the following Java code snippet:

public class InsertionSort {
    
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; 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;
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {5, 2, 7, 1, 3};
        insertionSort(arr);
        
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

What will be the output of the above code?

A) 1 2 3 5 7

B) 7 5 3 2 1

C) 5 2 7 1 3

D) 1 2 3 7 5

Explanation

The given code demonstrates the implementation of the Insertion Sort algorithm. The code starts by defining a static method insertionSort that takes an integer array arr as a parameter.

Inside the insertionSort method, a for loop is used to iterate over the array from index 1 (i = 1) to the end. This loop is responsible for performing the sorting logic.

For each iteration, the current element arr[i] is stored in a variable key. Then, a while loop is used to compare the current element with the elements on its left side. If any element is greater than the key, it is moved one position to the right (arr[j + 1] = arr[j]) until we find the correct position for the key.

Finally, the key is inserted at its correct position (arr[j + 1] = key) after all the necessary shifting operations are performed.

In the main method, an integer array arr is initialized with values {5, 2, 7, 1, 3}. The insertionSort method is called with this array as the argument, which sorts the array in ascending order.

After the sorting is completed, a for-each loop is used to print the elements of the sorted array separated by a space.

Thus, the output of the above code will be:

A) 1 2 3 5 7