Selection Sort

About

Imagine scanning a messy shelf of books to find the absolute shortest one, picking it up, and swapping its position with the very first book on the shelf. Then, you look at the remaining unsorted books, find the next shortest one, and swap it into the second position. Selection Sort repeatedly selects the minimum element from the unsorted portion of the array and moves it to the beginning.

![[sel.mp4]]

Complexities

Time Complexity:
- Best: $\huge $O (n^{2})$
- Worst/Average: $O (n^{2})$
Space Complexity: $O (1)$

Code Implementation

def selection_sort(arr):
    n = len(arr)
    
    # Move the boundary of the unsorted subarray
    for i in range(n):
        # Assume the first unsorted element is the minimum
        min_idx = i
        
        # Test against the rest of the array to find the true minimum
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
                
        # Swap the found minimum element with the first unsorted element
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
        
    return arr

Key Takeaways

The Memory Advantage (Minimal Swaps): While its time complexity is a disappointing $O (n^{2})$ across the board, Selection Sort does have a hidden superpower: it performs a maximum of $O (n)$ swaps. Bubble and Insertion sort can make up to $O (n^{2})$ writes/swaps. If write operations to memory are physically costly or slow, Selection Sort is highly efficient in terms of memory modification.
Why it is Unstable: The swap mechanism acts globally over long distances. If you swap the minimum element back into its correct spot, you might accidentally throw a duplicate element backward past another identical value.
When to Use It:
- Useful when your system memory has highly constrained write costs (like writing to certain types of flash memory or EEPROMs).
- Otherwise, avoid it in production due to its rigid $O (n^{2})$ behavior even on perfectly sorted inputs.