Question:

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

Your implementation must perform the following steps:

1. Find the minimum element in the unsorted part of the array and swap it with the element at the beginning of the unsorted part.
2. Repeat step 1 for the remaining unsorted part of the array until the entire array is sorted.

public class SelectionSort {

    public static int[] selectionSort(int[] arr) {
        // Your implementation here
        
    }
    
    public static void main(String[] args) {
        int[] arr = {5, 3, 2, 4, 1};
        int[] sortedArr = selectionSort(arr);
        
        // Print the sorted array
        for (int i = 0; i < sortedArr.length; i++) {
            System.out.print(sortedArr[i] + " ");
        }
    }
}

Explanation:

To implement the selection sort algorithm, follow these steps:

1. Declare a variable n and assign the length of the input array arr to it. This represents the number of elements in the array.

2. Iterate over the array from index 0 to n-1. Let the current index be i. This index represents the start of the unsorted part of the array.

3. Declare a variable minIndex and assign i to it. This will store the index of the minimum element found in the unsorted part of the array.

4. Iterate over the array from i+1 to n-1. Let the current index be j. This index represents the rest of the unsorted part of the array.

5. Inside the inner loop, check if the element at index j is less than the element at index minIndex. If so, update minIndex to j.

6. After the inner loop ends, swap the element at index i with the element at index minIndex using a temporary variable.

7. Repeat steps 3-6 until the outer loop ends, i.e., when i = n-1.

8. Finally, return the sorted array arr.

The time complexity of the selection sort algorithm is O(n^2), where n is the number of elements in the array. The space complexity is O(1), as it only requires a few variables for comparisons and swapping.

Answer (Java):

public static int[] 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;
    }

    return arr;
}

public static void main(String[] args) {
    int[] arr = {5, 3, 2, 4, 1};
    int[] sortedArr = selectionSort(arr);

    // Print the sorted array
    for (int i = 0; i < sortedArr.length; i++) {
        System.out.print(sortedArr[i] + " ");
    }
}

The output of the above code will be: 1 2 3 4 5.