Code & Robots, level 9
🫧 Sorting Algorithms
How does a computer put a jumbled list in order?
- How does a computer put a jumbled list in order? It follows a sorting algorithm, which is a set of steps for arranging items from smallest to largest or in some other order, and one of the simplest of these is called bubble sort. The NIST Dictionary of Algorithms and Data Structures describes it like this: compare each neighboring pair of items in turn, swap them if they are in the wrong order, and keep repeating passes through the list until a whole pass makes no swaps at all. On every pass, the largest item that is not yet in place drifts toward the end of the list, a little like a bubble rising through water. The algorithm never needs to look at more than two items at a time, which makes it easy to follow by hand.
- Watch bubble sort work on the list 5, 2, 8, 1, one comparison at a time. On the first pass, it compares 5 and 2, notices that they are in the wrong order and swaps them, which gives 2, 5, 8, 1. Next it compares 5 and 8, which are already in the correct order, so nothing moves at all. Then it compares 8 and 1 and swaps them, giving 2, 5, 1, 8, so the largest number now sits in its final position at the end. The second pass swaps 5 and 1, producing 2, 1, 5, 8, and the third pass swaps 2 and 1, producing 1, 2, 5, 8. A fourth pass travels through the whole list without finding anything to swap, so the algorithm stops, and the list is finally sorted. Altogether, bubble sort made four swaps and a dozen comparisons just to put four numbers in order.
- Bubble sort is easy to follow, but it gets slow on long lists, because it may have to compare neighbors over and over, pass after pass. For a list of n items, its work grows roughly like n times n, so doubling the length of a list can make it take about four times as long. Merge sort uses a smarter plan: it splits the list into two halves, sorts each half in the same way, and then merges the two sorted halves into a single sorted list. Its work grows roughly like n times the number of times you can cut n in half before reaching 1. For a list of a million items, n times n is a million million, while merge sort's count is only about 20 million, which is why programs that sort long lists use faster plans like merge sort.
Try it at home: Shuffle five playing cards and sort them by bubble sort together, swapping only neighbors, and count the swaps.
Questions and answers
Sorting Algorithms
- A set of steps for arranging items from smallest to largest is called a… sorting algorithm
- 👫 In bubble sort, which items get compared at each step? Two neighboring items (Bubble sort compares each neighboring pair in turn and swaps them if needed.)
- When does bubble sort stop? When a whole pass makes no swaps (A pass with no swaps means every neighboring pair is already in order, so the list is sorted.)
- 🫧 After the first pass of bubble sort, where does the largest number end up? At the end of the list (On each pass the largest number not yet in place drifts to the end.)
- Bubble sort is working on 5, 2, 8, 1. After it swaps 5 and 2, what is the list? 2, 5, 8, 1 (Only 5 and 2 trade places; 8 and 1 stay where they were for now.)
- 🔢 Bubble sort compares 5 and 8 in the list 2, 5, 8, 1. What happens? Nothing moves (5 and 8 are already in order, so bubble sort leaves them alone.)