18. Selection Sort: Concept and Implementation (O(N²))

Selection Sort improves slightly on Bubble Sort by minimizing the number of swaps.

Concept

Selection Sort divides the list into two parts: a sorted subarray and the remaining unsorted subarray. It repeatedly finds the minimum element from the unsorted part and moves it to the end of the sorted subarray.

Implementation Steps

1. Start at the first position i.
2. Scan the rest of the array (from i+1 to N) to find the index of the smallest element (min_idx).
3. Swap the element at i with the element at min_idx.
4. Increment i and repeat until the entire array is sorted.

python def selection_sort(arr): n = len(arr) for i in range(n): min_idx = i for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j

    # Swap the found minimum element with the current element (arr[i])
    arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr