- Explain why sorting is useful
- Carry out bubble, selection and insertion sort step by step
- Compare algorithms by the number of comparisons they make
The contacts in your phone are in alphabetical order, a game's leaderboard is ordered by points, and an online shop can list products by price. In all these cases the computer is sorting — arranging items in order by some rule. And, as we saw in the previous lesson, fast binary search only works on a sorted list. So how does a computer sort a list?
Rearranging the items of a list according to a rule — for example, in increasing or decreasing order, or alphabetically.
Bubble sort
In bubble sort, neighboring items are compared in pairs: if the left one is bigger than the right one, they swap places. One trip through the whole list is called a pass. After each pass, the largest remaining item “bubbles up” to the end of the list like a bubble in water. If a pass makes no swaps at all, the list is already sorted.
Sort the list [5, 1, 4, 2] in increasing order using bubble sort.
Show solutionHide solution
5 > 1 → swap: [1, 5, 4, 2]
5 > 4 → swap: [1, 4, 5, 2]
5 > 2 → swap: [1, 4, 2, 5] — 5 is in its place.
Pass 2:
1 < 4 → no change
4 > 2 → swap: [1, 2, 4, 5] — 4 is in its place.
Pass 3:
1 < 2 → no change. No swaps — the list is sorted: [1, 2, 4, 5].
In total 3 + 2 + 1 = 6 comparisons were made.
def bubble_sort(a):
a = a[:]
n = len(a)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped:
break
return a
print(bubble_sort([5, 1, 4, 2]))
print(sorted(['Murad', 'Aysel', 'Leyla', 'Elvin']))▸ Expected output
[1, 2, 4, 5] ['Aysel', 'Elvin', 'Leyla', 'Murad']
swapped remembers whether a pass made any swaps; if not, the algorithm stops early. Python's built-in sorted() function also sorts strings alphabetically.Selection sort
In selection sort, we find the smallest item in the unsorted part of the list and swap it with the first item of that part. This way, the sorted part on the left grows by one item at every step.
Sort [29, 10, 14, 37, 13] in increasing order using selection sort.
Show solutionHide solution
Step 2: in [29, 14, 37, 13] the smallest is 13; swap it with 29 → [10, 13, 14, 37, 29]
Step 3: in [14, 37, 29] the smallest is 14, and it is already in place.
Step 4: in [37, 29] the smallest is 29; swap it with 37 → [10, 13, 14, 29, 37].
Insertion sort
Insertion sort is like a card player arranging the cards in their hand: take the next card and insert it into its place among the cards already in order. It is very fast when the list is almost sorted.
Sort [4, 3, 5, 1] using insertion sort.
Show solutionHide solution
Take 3: 3 < 4, so put it before 4 → [3, 4, 5, 1]
Take 5: 5 > 4, it stays → [3, 4, 5, 1]
Take 1: 5, 4 and 3 each shift one place right, and 1 goes to the front → [1, 3, 4, 5].
Which algorithm is faster?
The speed of sorting is usually measured by the number of comparisons. Each of the three simple methods makes about n(n − 1) / 2 comparisons in the worst case: 45 for n = 10, but 499,500 for n = 1000. Make the list 10 times longer and the work grows about 100 times!
- Knumber of comparisons in the worst case
- nnumber of items in the list
| Method | Idea | Worst case | Already sorted list |
|---|---|---|---|
| Bubble | compare neighbors and swap them | n(n − 1) / 2 | n − 1 (with early stop) |
| Selection | find the smallest and put it in front | n(n − 1) / 2 | n(n − 1) / 2 |
| Insertion | insert each item into the sorted part | n(n − 1) / 2 | n − 1 |
Key points
- Sorting puts items in order by a rule; binary search needs a sorted list.
- Bubble sort compares neighbors; after each pass the largest item moves to the end.
- Selection sort repeatedly finds the smallest item and puts it at the front of the unsorted part.
- Insertion sort inserts each item into its place in the sorted part.
- Simple methods make n(n − 1) / 2 comparisons in the worst case; faster algorithms exist for large lists.
Check yourself
10 questions. Every correct answer earns XP.