Explain selection sort and its implementation in Java JDK 22 with example

Selection sort is a simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted portion of the array and swapping it with the element at the beginning of the unsorted portion. This process continues until the entire array is sorted. The key characteristic of selection sort is that it builds the sorted array one element at a time.

Here’s a step-by-step explanation of the selection sort algorithm:

1. Find the minimum element in the unsorted portion of the array.
2. Swap the minimum element with the first element of the unsorted portion.
3. Move the boundary between the sorted and unsorted portions one element to the right.
4. Repeat steps 1-3 until the entire array is sorted.

Now, let’s see an implementation of selection sort in Java:

import java.util.Arrays;

public class SelectionSortExample {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
// Find the index of the minimum element in the unsorted portion
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}

// Swap the minimum element with the first element of the unsorted portion
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
System.out.println("Original array: " + Arrays.toString(arr));
selectionSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}

In this implementation:

1. The `selectionSort` method takes an integer array `arr` as input and sorts it using the selection sort algorithm.
2. Inside the `selectionSort` method, two nested loops are used. The outer loop iterates over each element of the array except the last one. The inner loop finds the index of the minimum element in the unsorted portion of the array.
3. After finding the minimum element, it swaps it with the first element of the unsorted portion.
4. Finally, the `main` method demonstrates how to use the `selectionSort` method by sorting an example array and printing the original and sorted arrays.