1. Introduction

Selection Sort is a straightforward sorting algorithm that works by dividing the input list into two parts: a sorted sub-list and an unsorted sub-list. At every pass, the algorithm identifies the smallest (or largest, depending on sorting order) element from the unsorted sub-list and swaps it with the leftmost unsorted element, gradually moving the boundary between the sorted and unsorted sub-lists to the right.

2. Program Steps

1. Start with the first element of the array as the minimum.

2. Traverse through the array to find an element which is smaller than the current minimum.

3. If a smaller element is found, set it as the new minimum.

4. Once the end of the array is reached, swap the minimum element with the first element.

5. Move the boundary of the sorted sub-list one element to the right and repeat the above steps.

3. Code Program

public class SelectionSort {

    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int min_idx = i; // Assume the first element is the minimum
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[min_idx]) {
                    min_idx = j; // Update the index of the minimum element
                }
            }
            // Swap the minimum element with the first element
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("Sorted array:");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Output:

Sorted array:
11 12 22 25 64

4. Step By Step Explanation

1. The function selectionSort accepts an integer array arr as its argument.

2. The outer loop (i loop) goes through each element in the array assuming it's the smallest.

3. The inner loop (j loop) traverses the unsorted sub-array to find the actual minimum element.

4. If a smaller element is discovered during the inner loop, the index of the minimum element (min_idx) is updated.

5. Once the true minimum for the pass is identified, it's swapped with the element at the boundary of the sorted sub-list.

6. The process is repeated, incrementing the boundary of the sorted sub-list until the entire array is sorted.

7. The main method demonstrates sorting a sample array using the selectionSort method and then prints the sorted array.

Selection Sort, similar to Bubble Sort, is intuitive but inefficient for large datasets due to its O(n^2) average and worst-case time complexity.