Selection Sort in Data Structure

Selection Sort is a comparison-based sorting technique that divides the array into a sorted and unsorted part, repeatedly picking the minimum element from the unsorted part and moving it to the sorted part.

Dry Run Example

Sorting [29, 10, 14, 37]: In pass 1, the minimum (10) is found and swapped with the first element, giving [10, 29, 14, 37]. In pass 2, the minimum of the remaining unsorted part (14) is swapped into position, giving [10, 14, 29, 37]. The array is now sorted after the remaining pass confirms order.

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

Complexity

Key Points

• Performs at most n-1 swaps, making it useful when swap/write cost is high.
• Not stable in its standard form.
• Simple but inefficient for large datasets compared to O(n log n) algorithms.