The Algorithms - Python Python TheAlgorithms/Python

How Selection Sort Works

Find the minimum of the unsorted region, swap it to the front, repeat. O(n squared) always, but only O(n) swaps total.

5 stops ~10 min Verified 2026-05-05

What you will learn

Why selection sort makes exactly n-1 swaps regardless of input order and when that matters
How the inner scan finds the minimum index without moving any elements
Why the conditional swap on min_index != i avoids a redundant write on an already-in-place minimum
How the three doctest cases pin the contract on duplicates, empty input, and negatives
Why selection sort is not stable in its basic form and what that means for equal elements

Prerequisites

Comfort reading nested Python for loops with index variables
No prior knowledge of selection sort required

The story behind selection sort

Selection sort is textbook simple. Find the smallest element, move it to the front. Find the next smallest among what remains, move it to position two. Repeat until nothing is left to sort. The algorithm requires no auxiliary data structures and no complex invariants, which makes it one of the first sorting algorithms taught in computer science courses alongside bubble sort and insertion sort.

The distinctive property that sometimes makes selection sort worth choosing is its write count. Bubble sort can make O(n squared) swaps on a reverse-sorted input because every comparison that finds an out-of-order pair triggers a swap. Selection sort makes exactly n-1 swaps regardless of the input, because it only writes when it places a minimum into its final position. On hardware or storage where writes are much more expensive than reads, such as certain EEPROM or NOR flash devices, that O(n) write count is a genuine advantage.

The cost is that selection sort has no best case: even a sorted array requires the full O(n squared) comparisons because the algorithm must scan the entire unsorted region to confirm the minimum is already in place. It is also not stable in its basic form, because swapping a minimum past equal elements can change their relative order.

1 / 5

Signature and the Three-Case Doctest

sorts/selection_sort.py:1

The function takes a list of integers and returns it sorted ascending. Three doctests cover duplicates, empty input, and negatives.

At 34 lines, this is one of the shortest algorithm files in the repository. The signature accepts list[int] rather than a generic collection, which is narrower than insertion sort's MutableSequence[T: Comparable] but sufficient for the pedagogical purpose. Three doctests cover the three input shapes a learner typically checks first: a list with duplicates (line 9), the empty list (line 12), and a list with negative integers (line 15). The blank lines between examples are a stylistic choice by the contributor; the doctest module handles them correctly. There is no string or float test here because the type hint restricts the input to integers, and the contribution checklist allows a narrower type when the algorithm is being demonstrated for a specific domain.

Key takeaway

Three doctests pin duplicates, empty input, and negatives. The list[int] signature is narrower than a generic sort but sufficient for a focused pedagogical file.

def selection_sort(collection: list[int]) -> list[int]:
    """
    Sorts a list in ascending order using the selection sort algorithm.

    :param collection: A list of integers to be sorted.
    :return: The sorted list.

    Examples:
    >>> selection_sort([0, 5, 3, 2, 2])
    [0, 2, 2, 3, 5]

    >>> selection_sort([])
    []

    >>> selection_sort([-2, -5, -45])
    [-45, -5, -2]
    """

2 / 5

Finding the Minimum: Inner Scan Loop

sorts/selection_sort.py:19

The outer loop fixes the frontier at i. The inner scan from i+1 to length finds the minimum index without moving any element.

The outer loop runs from 0 to length - 2. The last element needs no pass because if all elements before it are in their correct positions, the last one must be too. Inside each outer iteration, min_index starts as i (the assumption is that the current front is the minimum until proven otherwise) and the inner loop scans rightward. Every time a smaller element is found at index k, min_index is updated. The scan never writes to the collection; it only reads. By the time the inner loop finishes, min_index points to the actual minimum of the unsorted region. That read-only scan is why selection sort's write count is so low: reads are cheap, and all the work of finding the minimum costs zero writes.

Key takeaway

The inner scan only reads; it never writes. All n-1 swaps happen outside the inner loop, making total writes O(n) regardless of input order.

    length = len(collection)
    for i in range(length - 1):
        min_index = i
        for k in range(i + 1, length):
            if collection[k] < collection[min_index]:
                min_index = k

3 / 5

The Conditional Swap

sorts/selection_sort.py:25

If min_index differs from i, swap the found minimum into position. The conditional avoids a self-swap when the minimum is already at the front.

The guard on line 25 is a small but meaningful optimization. Without it, every outer iteration would perform a swap even when the minimum is already at position i, adding an unnecessary write. With the guard, a swap only occurs when min_index differs from i, which means an already-sorted array incurs zero swaps. The swap itself is a single tuple-unpacking assignment on line 26, which is the idiomatic Python form: no temporary variable, no intermediate storage. The return on line 27 returns the same list object that was passed in, modified in place. A caller that holds a reference to the original list sees the sorted result without the function allocating a new one.

Key takeaway

The min_index != i guard skips self-swaps when the minimum is already in place. Total swaps are at most n-1, even on unsorted input.

        if min_index != i:
            collection[i], collection[min_index] = collection[min_index], collection[i]
    return collection

4 / 5

Why Selection Sort Has No Best Case

sorts/selection_sort.py:19

The inner scan always runs to the end of the unsorted region. A sorted input still requires all n(n-1)/2 comparisons.

Contrast selection sort with bubble sort and insertion sort. Bubble sort's swapped flag exits after one no-swap pass on an already-sorted list. Insertion sort's while loop condition fails immediately when the element being inserted is already larger than its left neighbor. Selection sort has no such early exit. The inner loop on lines 22 and 23 always runs from i+1 to length because the algorithm has no way to know whether any element to the right of i is smaller than collection[i] without checking each one. The only savings on a sorted input is that the if min_index != i guard fires every time, so no swaps occur, but the comparison count remains n(n-1)/2. That is why selection sort's best and worst case are both O(n squared).

Key takeaway

No early exit means O(n squared) comparisons always. The only input-sensitive saving is the swap guard, which eliminates n-1 writes on an already-sorted list.

    length = len(collection)
    for i in range(length - 1):
        min_index = i
        for k in range(i + 1, length):
            if collection[k] < collection[min_index]:
                min_index = k
        if min_index != i:
            collection[i], collection[min_index] = collection[min_index], collection[i]
    return collection

5 / 5

The main Guard: Minimal Driver

sorts/selection_sort.py:30

The interactive driver reads comma-separated integers, sorts them, and prints a labeled result. No doctest runner and no try/except.

This __main__ block is the most minimal driver in the sorts/ directory. It does not import doctest and does not wrap the input parsing in a try/except. Both are deliberate omissions at the contributor's discretion: the doctests run under pytest --doctest-modules in CI regardless of whether the file calls testmod() in __main__, and the three-line file is short enough that a contributor running it manually knows to supply integer input. The output label "Sorted List:" on line 34 differs from the debug f-string form used by heap sort and insertion sort; that too is a contributor style choice, not a convention. Compare this with sorts/merge_sort.py, which wraps everything in a try/except ValueError, and sorts/heap_sort.py, which guards against empty input before parsing.

Key takeaway

The minimal driver skips doctest.testmod() because CI runs doctests anyway. Each contributor chooses how much defensive code to add at the interactive layer.

if __name__ == "__main__":
    user_input = input("Enter numbers separated by a comma:\n").strip()
    unsorted = [int(item) for item in user_input.split(",")]
    sorted_list = selection_sort(unsorted)
    print("Sorted List:", sorted_list)

Your codebase next

Create code tours for your project

Intraview lets AI create interactive walkthroughs of any codebase. Install the free VS Code extension and generate your first tour in minutes.

Install Intraview Free

Signature and the Three-Case Doctest

Finding the Minimum: Inner Scan Loop

The Conditional Swap

Why Selection Sort Has No Best Case

The __main__ Guard: Minimal Driver

Create code tours for your project

The main Guard: Minimal Driver