Selection sort in Python

Selection sort finds the smallest item in the list and swaps it into the first position. Then it finds the smallest of the remaining items and swaps it into the second position, and so on until the end.

The program

def selection_sort(items):
    items = items.copy()               # leave the caller's list unchanged
    n = len(items)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            if items[j] < items[smallest]:
                smallest = j
        items[i], items[smallest] = items[smallest], items[i]
    return items

numbers = [64, 25, 12, 22, 11]
print(selection_sort(numbers))
print(numbers)
print(selection_sort([]))
print(selection_sort([3, -1, 3, 0]))

[11, 12, 22, 25, 64]
[64, 25, 12, 22, 11]
[]
[-1, 0, 3, 3]

How it works

• Everything before position i is already sorted and in its final place.
• The inner loop looks at the rest of the list and remembers the position of the smallest item in smallest.
• One swap then moves that item to position i. If it is already there, the item is swapped with itself, which changes nothing.
• The outer loop stops one item early: when all the other items are in place, the last one must be the largest.
• items.copy() makes the function return a new sorted list instead of changing the list you passed in.

Watching the passes

Printing the list after each swap shows the sorted part growing from the left:

items = [64, 25, 12, 22, 11]
for i in range(len(items) - 1):
    smallest = i
    for j in range(i + 1, len(items)):
        if items[j] < items[smallest]:
            smallest = j
    items[i], items[smallest] = items[smallest], items[i]
    print(items)

[11, 25, 12, 22, 64]
[11, 12, 25, 22, 64]
[11, 12, 22, 25, 64]
[11, 12, 22, 25, 64]

Selection sort always makes the same number of comparisons, about n²/2 for n items, even when the list is already sorted. So, like bubble sort, it is slow on long lists. It makes at most n - 1 swaps, which is fewer than bubble sort. It is not stable: the long swaps can change the order of equal items. In real code, use sorted(items).