AI Hints
Home›DSA in Python Tutorial›Simple Sorts
DSA in Python · Lesson 51 of 132

Selection Sort

Pick the smallest each time.

⏱ 2 min read▶ Video at 59:18🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Selection sort is how many people sort playing cards. Find the smallest card, and put it first. Then find the smallest of the rest, and put it second. Keep going until you run out of cards.

Selection Sort
From the video: Selection Sort
  • Find the smallest
  • Put it first
  • Repeat with the rest

Choosing the smallest

For each position, we search the rest of the list for the smallest item. Then we swap it into place. The part on the left grows, and it's always sorted. Run it. After each pass, one more item is in its final place, from left to right.

selection.pypython
def selection_sort(nums):
    n = len(nums)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            if nums[j] < nums[smallest]:
                smallest = j
        nums[i], nums[smallest] = nums[smallest], nums[i]
        print(f"pass {i + 1}: {nums}")

selection_sort([5, 2, 9, 1, 7])
Output
pass 1: [1, 2, 9, 5, 7]
pass 2: [1, 2, 9, 5, 7]
pass 3: [1, 2, 5, 9, 7]
pass 4: [1, 2, 5, 7, 9]

Selection sort cost

Selection sort is also O of N squared, because finding the smallest is a loop, inside a loop over every position. But it makes very few swaps, at most N, which can matter when moving items is expensive. Like bubble sort, it's mostly for learning.

keyvalue
TimeO(n²)
Swapsat most n
SpaceO(1)
Uselearning, few swaps

Summary

Selection sort picks the smallest remaining item, and swaps it into place. It's O of N squared, with few swaps. Next, insertion sort, which is surprisingly useful.

Key takeaways
  • Find the smallest
  • Swap it into place
  • O(n²)
Next up: Insertion Sort — slide each item into place