AP Computer Science Exam Question

Consider the following implementation of the selection sort algorithm in Java:

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            int minIdx = i;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] array = {5, 2, 7, 1, 3};

        selectionSort(array);

        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

What will be the output of the main method after executing the selectionSort method on the array array?

A) 1 2 3 5 7 B) 1 2 3 7 5 C) 5 2 7 1 3 D) 5 2 7 3 1

Explain the step-by-step process of how the selection sort algorithm sorts the given array.

Answer and Explanation

The correct answer is A) 1 2 3 5 7.

Step-by-step process of how the selection sort algorithm sorts the given array:

1. The outer loop iterates from index 0 to n-1 (where n is the length of the array). In each iteration, it selects the minimum element from the unsorted part of the array.
2. In the first iteration, the minimum element in the unsorted part is 1 (located at index 3). It swaps it with the element at index 0 (5).
3. After the first iteration, the array becomes [1, 2, 7, 5, 3].
4. In the second iteration, the minimum element in the unsorted part is 2 (located at index 1). It swaps it with the element at index 1 (2) itself.
5. After the second iteration, the array remains the same as [1, 2, 7, 5, 3] because the element at index 1 is already the minimum in the unsorted part.
6. In the third iteration, the minimum element in the unsorted part is 3 (located at index 4). It swaps it with the element at index 2 (7).
7. After the third iteration, the array becomes [1, 2, 3, 5, 7].
8. In the fourth iteration, the minimum element in the unsorted part is 5 (located at index 3). It swaps it with the element at index 3 (5) itself.
9. After the fourth iteration, the array remains the same as [1, 2, 3, 5, 7] because the element at index 3 is already the minimum in the unsorted part.

Therefore, the output of the main method after executing the selectionSort method on the array array will be "1 2 3 5 7" (option A).