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 sorting_selection_sort:
    def sort(self, nums: list[int]) -> list[int]:
        # `nums[:start]` is already sorted and final.
        for start in range(len(nums)):
            min_idx = start

            # Find the smallest value in the unsorted suffix.
            for i in range(start + 1, len(nums)):
                if nums[i] < nums[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.
            nums[start], nums[min_idx] = nums[min_idx], nums[start]

        return nums