Question:

Implement the selection sort algorithm to sort an array of integers in ascending order. Write a Java method named selectionSort that takes an array of integers as input and returns the sorted array.

Method Signature:

public static int[] selectionSort(int[] arr)

Input:

The input parameter arr is an array of integers. The length of the array is n (1 ≤ n ≤ 1000) and the elements of the array are integers (-10^9 ≤ arr[i] ≤ 10^9).

Output:

The method should return the sorted array in ascending order.

Example:

Input:

arr = {64, 25, 12, 22, 11}

Output:

[11, 12, 22, 25, 64]

Explanation:

The selection sort algorithm works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning. In each iteration, the smallest element is selected from the unsorted portion and swapped with the element at the current position.

Here are the steps to perform selection sort on the given input array:

1. Find the minimum element in the array from index 0 to n-1 (here, 11 is the smallest element at index 4).
2. Swap the minimum element (11) with the element at index 0. The array becomes: [11, 25, 12, 22, 64]
3. Repeat steps 1 and 2 for the remaining subarray from index 1 to n-1.
4. Find the minimum element in the subarray [25, 12, 22, 64] (12 is the smallest at index 2).
5. Swap the minimum element (12) with the element at index 1. The array becomes: [11, 12, 25, 22, 64]
6. Repeat steps 4 and 5 for the remaining subarray from index 2 to n-1.
7. Find the minimum element in the subarray [25, 22, 64] (22 is the smallest at index 3).
8. Swap the minimum element (22) with the element at index 2. The array becomes: [11, 12, 22, 25, 64]
9. Repeat steps 7 and 8 for the remaining subarray from index 3 to n-1.
10. Find the minimum element in the subarray [25, 64] (25 is the smallest at index 3).
11. Swap the minimum element (25) with the element at index 3. The array becomes: [11, 12, 22, 25, 64]
12. Repeat steps 10 and 11 for the remaining subarray from index 4 to n-1.
13. The array is now sorted in ascending order: [11, 12, 22, 25, 64].

Hence, the output of the selectionSort method when called with {64, 25, 12, 22, 11} as input will be [11, 12, 22, 25, 64].

Solution:

public static int[] selectionSort(int[] arr) {
    // Traverse through all array elements
    for (int i = 0; i < arr.length - 1; i++) {
        // Assume the current element is the minimum
        int minIndex = i;
        
        // Find the minimum element in the unsorted part of the array
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // Swap the minimum element with the current element
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
    
    return arr;
}