Question:

Implement a selection sort algorithm to sort an array of integers in ascending order.

Signature:

public static void selectionSort(int[] arr)

Example:

int[] arr = {64, 25, 12, 22, 11};
selectionSort(arr);
// Output: [11, 12, 22, 25, 64]

Explanation:

Selection sort works by repeatedly finding the minimum element from the unsorted portion of the array and swapping it with the first element of the unsorted portion. This process is repeated until the entire array is sorted.

Implementation:

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

    // Traverse through the array
    for (int i = 0; i < n - 1; i++) {
        // Find the minimum element in the remaining unsorted array
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // Swap the found minimum element with the first element of the unsorted portion
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

Complexity Analysis:

The time complexity of the selection sort algorithm is O(n^2) in the worst and average cases, where n is the number of elements in the array. The space complexity is O(1) as it operates directly on the input array without requiring additional space.