AP Computer Science Exam Question:

Consider the following Java code:

public class SelectionSort {

  public static void selectionSort(int[] arr) {
    int n = arr.length;

    for (int i = 0; i < n-1; i++) {
      int min_idx = i;
      for (int j = i+1; j < n; j++)
        if (arr[j] < arr[min_idx])
          min_idx = j;
        
      int temp = arr[min_idx];
      arr[min_idx] = arr[i];
      arr[i] = temp;
    }
  }

  public static void main(String[] args) {
    int[] arr = {64, 25, 12, 22, 11};
    selectionSort(arr);

    System.out.print("Sorted array: ");
    for (int i = 0; i < arr.length; i++)
      System.out.print(arr[i] + " ");
  }
}

Explain the purpose and functionality of the given selectionSort method. Use the provided Java code and provide a step-by-step explanation of how the selectionSort method works.

Create a markdown document with the question prompt and the answer.

Answer:

The selectionSort method is an implementation of the selection sort algorithm in Java. This algorithm divides the input array into two subarrays: a sorted subarray and an unsorted subarray. It repeatedly selects the minimum element from the unsorted subarray and swaps it with the first element of the unsorted subarray, effectively expanding the sorted subarray on each iteration.

Step-by-step explanation of the selectionSort method:

1. The selectionSort method takes an integer array arr as a parameter and sorts it in ascending order.
2. The method begins by initializing a variable n with the length of arr.
3. The outer loop iterates from i = 0 to n-1. It represents the index of the current element being considered for placement in the sorted subarray.
4. Inside the outer loop, a variable min_idx is initialized with the value of i. This variable stores the index of the minimum element found in the unsorted subarray.
5. The inner loop, starting from j = i+1, iterates through the unsorted subarray to find the minimum element. It compares the element at index j with the element at index min_idx. If the element at j is smaller, min_idx is updated with the index j.
6. After completing the inner loop, the minimum element of the unsorted subarray is found at arr[min_idx].
7. The value at arr[min_idx] is stored in a temporary variable temp.
8. The value at arr[min_idx] is replaced with the value at arr[i], effectively swapping the minimum element with the first element of the unsorted subarray.
9. Finally, the value stored in temp is assigned to arr[i], placing the minimum element in the correct position in the sorted subarray.
10. The outer loop continues until all elements have been processed and the array is sorted in ascending order.
11. In the main method, an example array [64, 25, 12, 22, 11] is created.
12. The selectionSort method is called with the example array as an argument to sort it in ascending order.
13. The sorted array is then displayed as output.

Note: The selection sort algorithm has a time complexity of O(n^2) in worst and average cases.