Understanding Selection Sort

Selection Sort is a simple and intuitive comparison-based sorting algorithm. It works by dividing the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list, and an unsorted sublist of the remaining items that occupy the rest of the list.

How it works

1. Find the Minimum: The algorithm searches the entire unsorted portion of the array to find the smallest (minimum) element.
2. Swap: Once found, it swaps this minimum element with the first element of the unsorted portion, thus incorporating it into the sorted portion.
3. Advance: The boundary of the sorted portion shifts one element to the right, and the process repeats until the entire list is sorted.

Mathematical Complexities

• Best, Worst & Average Case Complexity O(N²): Since we must always scan the unsorted list to find the minimum element, it performs O(N²) comparisons regardless of the initial order.
• Space Complexity O(1): In-place sorting algorithm requiring constant extra space.

💡 Note: Selection Sort is notorious for its O(N²) complexity, but it is very simple and performs a maximum of O(N) swaps, which makes it useful in systems where writing to memory is highly expensive compared to reading.