Selection sort

Problem¶

Implement selection sort for a Python list.

Key trick¶

Find the minimum unsorted element and place it at the next output position.

Trap¶

Selection sort remains \(O(n^2)\) on sorted input and the usual swap-based implementation is unstable.

Why is it interesting?¶

It performs only \(O(n)\) swaps, but its quadratic comparisons make it unsuitable for normal Python code.

Python solution¶

class sort_selection_sort:
    def sort(self, nums: list[int]) -> list[int]:
        # Preserve the caller's input.
        arr = nums[:]

        # `arr[:start]` is already sorted and final.
        for start in range(len(arr)):
            min_idx = start

            # Find the smallest value in the unsorted suffix.
            for i in range(start + 1, len(arr)):
                if arr[i] < arr[min_idx]:
                    min_idx = i

            # Place that minimum at the boundary of the sorted prefix.
            # This swap is why standard selection sort is not stable.
            arr[start], arr[min_idx] = arr[min_idx], arr[start]

        return arr