AP Computer Science Exam Question:

Consider the following code that implements the selection sort algorithm:

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

  public static void main(String[] args) {
    int[] arr = {15, 7, 3, 22, 11};
    selectionSort(arr);
    for (int num : arr) {
      System.out.print(num + " ");
    }
  }
}

In the code above, the selectionSort method sorts an array of integers in ascending order using the selection sort algorithm. Consider the given array int[] arr = {15, 7, 3, 22, 11};.

a) What will be the output of the program when executed?

Answer:

The program will output 3 7 11 15 22 .

The selection sort algorithm works by dividing the array into two subarrays: the sorted part and the unsorted part. In each iteration, the algorithm finds the minimum element from the unsorted part and swaps it with the first element of the unsorted part. This process repeats until the entire array is sorted.

Now let's explain the step-by-step execution of the code:

1. The main method initializes the array arr with elements: 15, 7, 3, 22, 11.

2. The selectionSort method is called with the arr array as a parameter.

3. The outer loop of the selection sort algorithm iterates from i=0 to i<arr.length-1 (excluding the last element).

4. In the first iteration (i=0), the minIndex is initialized as i (0).

5. The inner loop iterates from j=i+1 to j<arr.length (from 1 to 4).

6. The condition arr[j] < arr[minIndex] is evaluated for each j.

7. When j=1, arr[1] (7) is less than arr[0] (15), so minIndex is updated to 1.

8. The inner loop continues until j=4, where arr[4] (11) is less than arr[1] (7), updating minIndex to 4.

9. At the end of the inner loop, the minimum element in the unsorted part (arr[minIndex]) is found.

10. The minimum element (3) is swapped with the first element of the unsorted part (15), resulting in arr = {3, 7, 15, 22, 11}.

11. The outer loop continues to the next iteration (i=1), repeating the process.

12. In the second iteration, the new minIndex is determined and the element at that index is swapped with the second element of the unsorted part.

13. The process repeats until all elements are sorted.

14. Finally, the sorted array arr is printed: 3 7 11 15 22 .

Therefore, the output of the program when executed will be 3 7 11 15 22 .