AP Computer Science Exam Question:

public class SelectionSort {
  
  public static void selectionSort(int[] arr) {
    // your implementation here
  }
  
  public static void main(String[] args) {
    int[] numbers = {5, 9, 2, 1, 8, 6, 3, 7, 4};
    
    // Sort the numbers array using the selectionSort method
    
    // Print the sorted array
    System.out.println("Sorted Array: " + Arrays.toString(numbers));
  }
}

Please complete the selectionSort method to sort the array arr using the selection sort algorithm. Implement the method, and then call it in the main method to sort the numbers array. Finally, print the sorted array.

Answer with Step-by-step Explanation:

To sort the arr array using the selection sort algorithm, follow these steps:

1. Initialize two variables: minIndex and temp.
2. Iterate through the array from the first index (i = 0) to the second-to-last index (i < arr.length - 1).
3. Within the outer loop, set minIndex to the current index (i).
4. Then, start another loop from the next index of i to the end of the array (j = i + 1; j < arr.length; j++).
5. Inside the inner loop, check if the element at index j is less than the element at index minIndex.
   • If true, update minIndex to j.
6. After the inner loop finishes, check if minIndex is not equal to i. This indicates that there is another smaller element at index minIndex.
   • If true, swap the elements at minIndex and i using the temp variable.
7. Finally, after the outer loop completes, the array will be sorted in ascending order.

Here is the complete implementation of the selectionSort method to sort the arr array:

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;
      }
    }
    if (minIndex != i) {
      int temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
}

In the main method, call the selectionSort method to sort the numbers array, and then print the sorted array:

int[] numbers = {5, 9, 2, 1, 8, 6, 3, 7, 4};
selectionSort(numbers);
System.out.println("Sorted Array: " + Arrays.toString(numbers));

This will output:

Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9]

The numbers array is now sorted in ascending order using the selection sort algorithm.