Python selection sort

Select the smallest remaining value for each position.

Python

def selection_sort(values):
    result = values.copy()
    for i in range(len(result)):
        smallest = i
        for j in range(i + 1, len(result)):
            if result[j] < result[smallest]:
                smallest = j
        result[i], result[smallest] = result[smallest], result[i]
    return result

print(selection_sort([3, 1, 2]))
assert selection_sort([]) == []
assert selection_sort([2, 2, 1]) == [1, 2, 2]

Output

[1, 2, 3]

Explanation

Selection sort scans the unsorted suffix for a minimum, then exchanges it with the first position in that suffix.

Unlike insertion sort, this simple swapping version is not stable: swapping a distant minimum can reverse the original order of equal keys.

Explore the dry run

Guided walkthroughReady

1def selection_sort(values):

2 result = values.copy()

3 for i in range(len(result)):

4 smallest = i

5 for j in range(i + 1, len(result)):

6 if result[j] < result[smallest]:

7 smallest = j

8 result[i], result[smallest] = result[smallest], result[i]

9 return result

11print(selection_sort([3, 1, 2]))

12assert selection_sort([]) == []

13assert selection_sort([2, 2, 1]) == [1, 2, 2]

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Create the working copy.	`result = [3, 1, 2]`	—
At i=0, find minimum 1 at index 1.	`smallest = 1`	—
Swap it into index 0.	`result = [1, 3, 2]`	—
At i=1, find minimum 2 at index 2.	`smallest = 2`	—
Swap into index 1; the final pass swaps the last item with itself.	`result = [1, 2, 3]`	—
Print the result.	`result = [1, 2, 3]`	[1, 2, 3]

Cost and common mistakes

Θ(n²) comparisons even for sorted input; O(n) copy storage and O(n) swaps.

Reset smallest for each outer iteration.
Do not call this version stable just because equal values compare equal.

Try it yourself

How many comparisons are made for four values?

Reveal answer and reasoning

The suffix scans make 3 + 2 + 1 = 6 comparisons.

Python selection sort

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading