Navigation
Exploring how computers organize data by swapping neighboring items.
Imagine you have a row of messy books on a shelf, but you can only use two hands to compare two books at a time. How could you get the tallest book to the very end without taking everything off the shelf?
Computers often need to put things in order, like sorting high scores in a game or names in a contact list. One of the simplest ways to do this is called Bubble Sort. The name comes from the way the largest items 'bubble' up to the end of the list, just like bubbles rising in a soda! The secret to Bubble Sort is the Neighbor Rule: you only ever look at two items sitting right next to each other. If the item on the left is larger than the item on the right (), you swap them. If they are already in the right order, you leave them alone and move to the next pair.
Let's look at a tiny list of two numbers: .
1. Look at the first pair: and . 2. Compare them: Is ? Yes. 3. Action: Swap them! 4. Result: The list is now .
Because was the larger number, it moved (or 'bubbled') to the right.
Quick Check
In a Bubble Sort, if you are looking at the pair [4, 7], do you perform a swap? Why or why not?
Answer
No, because 4 is already smaller than 7, so they are in the correct order.
To sort a longer list, the computer starts at the very beginning and moves through the entire list once. This is called a pass. During a pass, the computer compares the first and second items, then the second and third, then the third and fourth, and so on. By the time the computer reaches the end of the list for the first time, the largest number is guaranteed to have bubbled all the way to the last position. However, the rest of the numbers might still be messy! This is why we usually need to take multiple passes through the list to get everything perfectly aligned.
Let's try one full pass on the list .
1. Compare 4 and 1: , so swap. List: . 2. Compare 4 and 3: , so swap. List: . 3. Compare 4 and 2: , so swap. List: .
Notice that after one pass, the largest number () is now at the very end!
Quick Check
After the first pass of the list [3, 5, 1], what will the list look like?
Answer
[3, 1, 5]
How does the computer know when to stop? It doesn't just guess! The computer keeps track of whether any swaps happened during a pass. If the computer goes through the entire list from start to finish and makes zero swaps, it knows the list is perfectly sorted. If even one swap happens, it must go back and try another pass. This is why Bubble Sort can be slow for huge lists—it has to keep checking and re-checking until everything stays exactly where it is.
Imagine we have the list .
1. Pass 1: Compare 2 and 1 (Swap!). Compare 2 and 3 (No swap). List is now . 2. Even though it looks sorted to us, the computer saw a swap, so it must do Pass 2. 3. Pass 2: Compare 1 and 2 (No swap). Compare 2 and 3 (No swap). 4. Since zero swaps occurred in Pass 2, the computer officially stops. The list is sorted!
What is the main rule for swapping two numbers in a Bubble Sort?
If you perform one full pass on the list , which number is guaranteed to be in its correct final position?
A computer knows a list is sorted if it completes a full pass without making any swaps.
Review Tomorrow
Tomorrow, try to explain the 'Neighbor Rule' to a friend or family member using coins of different sizes.
Practice Activity
Grab 5 random playing cards. Try to sort them from smallest to largest using the Bubble Sort method. Count how many 'passes' it takes you!