Java Implementation of Selection Sort Algorithm¶

What is Selection Sort?¶

Selection Sort is a simple and intuitive sorting algorithm. Its core idea is similar to organizing playing cards: each time, pick the smallest (or largest) card from the unsorted pile and place it at the end of the sorted pile. Repeat this process until all cards are sorted.

Basic Idea of Selection Sort¶

Suppose we have an array arr that needs to be sorted in ascending order. The steps are as follows:
1. Outer Loop: Traverse each position i of the array (starting from 0). This position represents the “end of the sorted part,” and we need to determine the element at position i.
2. Inner Loop: In the unsorted part (from i+1 to the end of the array), find the index minIndex of the smallest element.
3. Swap Elements: Swap the element at position i with the element at minIndex. Now, the element at position i is confirmed to be the smallest in the unsorted part.
4. Repeat: Continue the outer loop until all elements are sorted.

Java Code Implementation¶

Here is the Java code for selection sort with detailed comments:

public class SelectionSort {
    // Selection sort method
    public static void selectionSort(int[] arr) {
        int n = arr.length; // Length of the array

        // Outer loop: Traverse each position i that needs to be determined (from 0 to n-1)
        for (int i = 0; i < n - 1; i++) {
            // Initialize the index of the minimum value as the current position i
            int minIndex = i;

            // Inner loop: Find the minimum value in the unsorted part (from i+1 to n-1)
            for (int j = i + 1; j < n; j++) {
                // If current element arr[j] is smaller than the element at minIndex, update minIndex
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // Swap the minimum element in the unsorted part with the element at position i
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    // Test method
    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        System.out.println("Array before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        selectionSort(arr); // Call selection sort

        System.out.println("\nArray after sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Code Explanation¶

1. Outer Loop: for (int i = 0; i < n - 1; i++)
   - The variable i represents the “end position of the sorted part.” When i = 0, we need to determine the element at position 0; when i = n-2, only the last element remains unsorted, and the loop ends.

2. Inner Loop: for (int j = i + 1; j < n; j++)
   - The inner loop starts from i+1 and traverses to the end of the array to find the minimum value in the unsorted part.

3. Finding the Minimum Value: if (arr[j] < arr[minIndex]) { minIndex = j; }
   - The variable minIndex always records the index of the smallest value found so far. Initially, it is assumed that the element at position i is the smallest. If a smaller element is found later, minIndex is updated.

4. Swapping Elements: temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp;
   - Swap the element at position i with the minimum value in the unsorted part. Now, the element at position i is confirmed to be the minimum, and the next loop iteration begins.

Sorting Process Example¶

Taking the array {64, 25, 12, 22, 11} as an example, the sorting process is demonstrated step by step:

• Initial Array: [64, 25, 12, 22, 11]
• First Round (i=0): The inner loop finds the minimum in [1,2,3,4]. The smallest element is 11 (index 4). After swapping, the array becomes [11, 25, 12, 22, 64].
• Second Round (i=1): The inner loop finds the minimum in [2,3,4]. The smallest element is 12 (index 2). After swapping, the array becomes [11, 12, 25, 22, 64].
• Third Round (i=2): The inner loop finds the minimum in [3,4]. The smallest element is 22 (index 3). After swapping, the array becomes [11, 12, 22, 25, 64].
• Fourth Round (i=3): The inner loop finds the minimum in [4] (only 64). No swap is needed, and the array remains unchanged.

Final Sorted Result: [11, 12, 22, 25, 64].

Time Complexity¶

The time complexity of selection sort is O(n²) (where n is the length of the array). Regardless of the initial state of the array, the inner loop performs approximately n²/2 comparisons. Thus, it is suitable for sorting small-scale data.

Summary¶

The core of selection sort is “selecting the minimum value each time” and gradually building the sorted array through element swaps. It has a simple logic and easy-to-implement code, making it ideal for beginners to understand the basic ideas of sorting algorithms. Through the above examples and code, you should now have a solid grasp of the Java implementation of selection sort!