Concept Overview

Selection Sort is a simple, in-place comparison-based sorting algorithm. It works by repeatedly finding the minimum element from the unsorted portion of the array and placing it at the beginning. The algorithm divides the array into a sorted and an unsorted region, gradually building the sorted region.

How It Works

• Start with the entire array as the unsorted region.
• In each iteration, find the smallest element in the unsorted region.
• Swap this minimum element with the first element of the unsorted region.
• Move the boundary of the sorted region one step forward.
• Repeat until the unsorted region is empty.

Time and Space Complexity

• Time Complexity:
  • Best Case: O(n²) (array is already sorted)
  • Average Case: O(n²)
  • Worst Case: O(n²) (array is reverse sorted)
• Space Complexity: O(1) (in-place sorting, only uses a constant amount of extra memory)

Why Use Selection Sort?

• Purpose: Selection Sort is intuitive and easy to implement, making it suitable for educational purposes or small datasets (n < 1000).
• Relevance: It performs well when the cost of swapping is low, as it minimizes the number of swaps (at most n-1 swaps).
• Limitations: Its quadratic time complexity makes it inefficient for large datasets compared to advanced algorithms like Quick Sort or Merge Sort.

Java Implementation

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            // Find the minimum element in the unsorted region
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap the found minimum element with the first element of the unsorted region
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        selectionSort(arr);
        System.out.println("Sorted array: " + java.util.Arrays.toString(arr));
    }
}

Best Practices and Pitfalls

• Best Practice: Use when the dataset is small or when minimizing swaps is critical (e.g., in memory-constrained systems).
• Pitfall: Avoid using Selection Sort for large datasets due to its O(n²) complexity. Always check for edge cases like empty arrays or arrays with duplicate elements.