Python selection sort

Select the smallest remaining value for each position.

On this page

Before you start

Lists, indexing, and nested loops.

Select the smallest remaining value for each position.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

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]

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

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]

Behind the scenes

How Python processes this code

Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.

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.