AP Computer Science Exam Question:

Consider the following Java code snippet that implements the selection sort algorithm to sort an array in ascending order:

public class SelectionSort {
    
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            int minIndex = i;
            for (int j = i+1; j < n; 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[] nums = {5, 2, 8, 1, 9};
        selectionSort(nums);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }
}

Explain the steps involved in the selection sort algorithm and analyze the output of the above code snippet.

Answer:

The selection sort algorithm is an in-place sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the array and swapping it with the first element of the unsorted part. This process is repeated for each element until the entire array is sorted.

The steps involved in the selection sort algorithm are as follows:

1. Initialize a variable n with the length of the array.
2. Iterate over the elements of the array from index 0 to n-1.
3. Assume the current element at index i is the minimum element and assign minIndex = i.
4. Within the nested loop starting from i+1 to n-1, compare each element with the current minimum element.
5. If an element (arr[j]) is found to be smaller than the current minimum element (arr[minIndex]), update minIndex to j.
6. After the inner loop, swap the current minimum element (arr[minIndex]) with the first element of the unsorted part (arr[i]).
7. Repeat steps 3 to 6 until the entire array is sorted.

By executing the above code snippet, the output will be: 1 2 5 8 9.

Explanation of the output:

1. selectionSort(nums) is called, where nums = {5, 2, 8, 1, 9}.
2. In the outer loop, the iteration begins from i = 0.
3. The inner loop finds 1 as the minimum element and assigns minIndex = 3.
4. The minimum element 1 is swapped with the first element 5: {1, 2, 8, 5, 9}.
5. The array after the first iteration becomes {1, 2, 8, 5, 9}.
6. In the next iteration, i = 1, and the inner loop finds 2 as the minimum element. Since 2 is already at the correct position, no swapping occurs.
7. The array after the second iteration remains unchanged as {1, 2, 8, 5, 9}.
8. Similarly, in the next iterations, the minimum elements are 5, 8, and 9, respectively, but no swapping occurs as they are already at the correct positions.
9. After all iterations, the final sorted array is {1, 2, 5, 8, 9}.

Thus, the output of the above code is 1 2 5 8 9.