Python programs / Searching and sorting / Selection sort

Python Program for Selection Sort

Beginner Searching and sorting Time O(n²) Space O(1)

Sorts a list by finding the smallest item left and swapping it to the front of the unsorted part, one place at a time.

Selection sort keeps a sorted part at the front of the list and an unsorted part after it. On each pass it selects the smallest item of the unsorted part and swaps it to the front of that part, so the sorted part grows by one item. In [38, 27, 43, 3, 9, 82, 10], the first pass finds 3, the smallest item, and swaps it with 38 at the front: [3, 27, 43, 38, 9, 82, 10].

Program

def selection_sort(items):
    """Sort items in place, from smallest to largest."""
    n = len(items)
    for i in range(n - 1):
        smallest = i  # index of the smallest item found so far
        for j in range(i + 1, n):
            if items[j] < items[smallest]:
                smallest = j
        items[i], items[smallest] = items[smallest], items[i]


numbers = [38, 27, 43, 3, 9, 82, 10]
print("Before:", numbers)
selection_sort(numbers)
print("After: ", numbers)

Open in the editor Download selection_sort.py

Output

Before: [38, 27, 43, 3, 9, 82, 10]
After:  [3, 9, 10, 27, 38, 43, 82]

How it works

  1. n is the number of items, and i is where the unsorted part starts: everything before index i is in its final place. The loop stops one item before the end, because once all the others are placed, the last item is too.
  2. The search for the smallest item of the unsorted part starts with its first item, at index i.
  3. The inner loop looks at every item after it and remembers the index of any item smaller than the smallest found so far.
  4. The smallest item swaps places with items[i], the first item of the unsorted part. It's now in its final place, and the sorted part is one item longer. a, b = b, a swaps two values in one line (tuples).
  5. The program prints the list, sorts it in place, and prints it again.

The list after each pass:

Pass i Smallest item left List after the swap
1 0 3, at index 3 [3, 27, 43, 38, 9, 82, 10]
2 1 9, at index 4 [3, 9, 43, 38, 27, 82, 10]
3 2 10, at index 6 [3, 9, 10, 38, 27, 82, 43]
4 3 27, at index 4 [3, 9, 10, 27, 38, 82, 43]
5 4 38, at index 4 [3, 9, 10, 27, 38, 82, 43]
6 5 43, at index 6 [3, 9, 10, 27, 38, 43, 82]

In pass 5, 38 is already the smallest item left, so it swaps with itself and nothing changes.

Time and space complexity

TimeO(n²)
Extra spaceO(1)

Selection sort makes the same comparisons whatever the order of the list: (n − 1) + (n − 2) + … + 1 = n(n − 1)/2, which is 21 for 7 items. So its best, average and worst cases are all O(n²); unlike bubble sort and insertion sort, it can't finish early on a sorted list. It makes at most n − 1 swaps, though, which matters when moving an item is costly. It sorts in place with a few variables: O(1) extra space. It is not stable: the swap can carry an item past an equal one. Sorting [5, 5, 2] swaps the first 5 with the 2, so the two 5s end up in the opposite order.

Other ways to write it

With min()

min() can find the index of the smallest item left in one line: key=lambda k: items[k] makes it compare the indexes by the items at them (lambda).

def selection_sort(items):
    for i in range(len(items) - 1):
        smallest = min(range(i, len(items)), key=lambda k: items[k])
        items[i], items[smallest] = items[smallest], items[i]

numbers = [38, 27, 43, 3, 9, 82, 10]
selection_sort(numbers)
print(numbers)

Building a new list

This version leaves the original list alone: it moves the smallest item from a copy to a new list until the copy is empty.

def selection_sort(items):
    rest = items.copy()
    result = []
    while rest:
        smallest = min(rest)
        rest.remove(smallest)
        result.append(smallest)
    return result

print(selection_sort([38, 27, 43, 3, 9, 82, 10]))

Try it yourself

  • Print the list at the end of each pass and compare it with the table above.
  • Sort from largest to smallest by looking for the largest item on each pass.
  • Count the comparisons for this list and for one that's already sorted: both make 21.
  • Sort [(5, "a"), (5, "b"), (2, "c")] comparing only the numbers (items[j][0] < items[smallest][0]), and see the two 5s change order.

More searching and sorting programs

Share this program