Understanding Selection Sort Algorithm (with Examples in Java)

Selection Sort: A Step-by-Step Guide

Selection Sort is a straightforward sorting algorithm. It repeatedly finds the minimum element from the unsorted part of the list and places it at the beginning. This process continues until the entire list is sorted.

How Selection Sort Works

Let's illustrate with an example, sorting this array in ascending order:

Iteration 1:

The goal is to place the smallest element at the beginning. We start by assuming the first element is the minimum.

We compare the current minimum with each subsequent element, updating the minimum if a smaller element is found.

This continues until the actual minimum is identified.

Finally, we swap the minimum element with the first element.

The first element is now sorted. Subsequent iterations will only consider the unsorted portion.

Subsequent Iterations:

This process repeats for each remaining unsorted element.

The algorithm iterates n-1 times (where n is the array's length). After the fifth iteration (for a six-element array), the last element is implicitly sorted.

Selection Sort Implementation (Java):

<code class="language-java">import java.util.Arrays;

public class SelectionSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        selectionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static void selectionSort(int[] arr) {
        int size = arr.length;

        // Iterate through the array size-1 times
        for (int i = 0; i < size - 1; i++) {
            int minIndex = i;
            // Find the minimum element in the unsorted part
            for (int j = i + 1; j < size; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap the minimum element with the first unsorted element
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}</code>

Output:

Unsorted array: [8, 2, 6, 4, 9, 1] Sorted array: [1, 2, 4, 6, 8, 9]

Complexity Analysis:

• Time Complexity: O(n²) in all cases (best, average, worst). The nested loops always execute a fixed number of times regardless of the input order.
• Space Complexity: O(1). It's an in-place algorithm, requiring constant extra space.

Conclusion:

Selection Sort's O(n²) time complexity makes it inefficient for large datasets. It's best suited for small arrays or situations where simplicity is prioritized over performance.

The above is the detailed content of Understanding Selection Sort Algorithm (with Examples in Java). For more information, please follow other related articles on the PHP Chinese website!