Selection Sort Algorithm in Java

1. Introduction

Selection Sort is a simple comparison-based sorting algorithm. The main idea behind this algorithm is to divide the input list into two parts: a sorted part and an unsorted part. Initially, the sorted part is empty and the unsorted part contains all the elements. The algorithm repeatedly selects the smallest (or largest, depending on sorting order) element from the unsorted part and moves it to the end of the sorted part.

2. Implementation Steps

1. Begin with the leftmost element of the array and compare it with every other element to its right.

2. During this process, find the minimum (or maximum) element from the unsorted part.

3. Swap this minimum (or maximum) element with the leftmost element.

4. Move the boundary between the sorted and unsorted parts of one element to the right and repeat until the entire array is sorted.

3. Implementation in Java

public class SelectionSort {
    // Selection Sort function
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int min_idx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[min_idx]) {
                    min_idx = j;
                }
            }
            // Swap the minimum element with the first element
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }
    // Function to print the array
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Original array:");
        printArray(arr);
        selectionSort(arr);
        System.out.println("Sorted array:");
        printArray(arr);
    }
}

Output:

Original array:
64 34 25 12 22 11 90
Sorted array:
11 12 22 25 34 64 90

Explanation:

1. The selectionSort function sorts an array using the Selection Sort algorithm.

2. The outer loop runs for n-1 times, where n is the length of the array. This loop maintains the boundary between the sorted and unsorted parts of the array.

3. The inner loop compares each element of the unsorted part with the current minimum element, updating the min_idx whenever it finds a smaller element.

4. After the inner loop completes for each iteration of the outer loop, we've found the minimum element in the unsorted part. We then swap this minimum element with the first element in the unsorted part.

5. printArray is a utility function to print the elements of an array.

6. The main function demonstrates the Selection Sort algorithm on a sample array.