Navigation
Learning how to sort by repeatedly finding the smallest item and moving it to the front.
Imagine you are a librarian with a messy pile of books of different heights. Instead of moving books randomly, what if you could always find the shortest book and put it exactly where it belongs in one move?
In computer science, Selection Sort is an algorithm that organizes a list by repeatedly finding the smallest (minimum) item. Imagine you have a row of numbers. To start, you look at every single number to find the smallest one. Once you find it, you swap it with the number in the first position. Now, the first position is 'sorted,' and you never have to move it again! You then repeat this for the rest of the list. If you have items, you keep searching the 'unsorted' part until everything is in order.
Let's sort three numbers: . 1. Scan: Look at all numbers. The minimum is . 2. Swap: Swap with the first number (). The list is now . 3. Next Step: The is now in the 'sorted' zone. Look at the remaining . 4. Scan: The minimum of the remaining is . 5. Swap: Swap with . The list is now . 6. Finish: Only one number is left, so the list is sorted!
Quick Check
In Selection Sort, what do we do immediately after finding the smallest number in the unsorted section?
Answer
We swap it with the first number in the unsorted section.
As Selection Sort runs, it mentally divides your list into two parts: the Sorted Side (on the left) and the Unsorted Side (on the right). Think of an invisible wall moving from left to right. Every time you find the minimum of the unsorted side and swap it to the front, the wall moves one step to the right. This is different from Bubble Sort, which swaps neighbors constantly. Selection Sort is more 'decisive'—it looks at everything first, then makes exactly one swap per position.
Sort the list: . 1. Pass 1: Smallest is . Swap with . List: . (The is the wall). 2. Pass 2: Smallest in unsorted is . Swap with . List: . 3. Pass 3: Smallest in unsorted is . Swap with . List: . 4. Pass 4: Smallest in unsorted is . It's already in place! No swap needed. List: . 5. Result: All numbers are sorted.
Quick Check
If a list has 5 items, how many times do we search for the minimum value?
Answer
4 times (the last item is automatically sorted once the others are in place).
Why use Selection Sort? While both are basic algorithms, they behave differently. Bubble Sort is like a wave; it compares neighbors and 'bubbles' the largest item to the end. It performs many, many swaps. Selection Sort is like a scavenger hunt; it scans the whole area for the prize (the smallest number) and then puts it in the basket. Selection Sort usually performs far fewer swaps than Bubble Sort, which makes it 'cheaper' if moving items is hard or slow!
Imagine sorting . - Bubble Sort would swap and , then and , then and ... it takes many swaps just to move the to the end! - Selection Sort simply finds the , swaps it with the , and in one single swap, the first position is perfectly sorted: . Selection Sort is much more efficient with swaps!
What is the first step in a Selection Sort pass?
If we are sorting using Selection Sort, what will the list look like after the first swap?
Selection Sort usually performs more swaps than Bubble Sort.
Review Tomorrow
In 24 hours, try to explain to a friend why Selection Sort is like a 'scavenger hunt' for the smallest number.
Practice Activity
Take a deck of cards, pull out 5 random cards, and sort them using Selection Sort. Count how many swaps you make!