Bubble, Selection and Insertion Sort
28 min · Beginner
Need help? Ask a tutor on WhatsApp (opens in a new tab)Sorting puts items in order so that searching, grouping and comparing become easy. The three simple sorts are slow on big lists, but they teach comparing, swapping and counting cost, and interviewers still ask for them.
Bubble sort: swap neighbours
Bubble sort is a sort that repeatedly compares neighbouring items and swaps them when they are out of order, so large values drift to the end of the list one pass at a time.
Walk along the list and swap any two neighbours that are out of order. After one pass the largest value sits at the end, so the next pass can stop one place earlier.
def bubble_sort(items): n = len(items) for end in range(n - 1, 0, -1): swapped = False for i in range(end): if items[i] > items[i + 1]: items[i], items[i + 1] = items[i + 1], items[i] swapped = True if not swapped: break
marks = [64, 34, 25, 12, 22]bubble_sort(marks)print(marks)Example 1 · Bubble sort, pass by pass
marks = [5, 1, 4, 2, 8]n = len(marks)for end in range(n - 1, 0, -1): for i in range(end): if marks[i] > marks[i + 1]: marks[i], marks[i + 1] = marks[i + 1], marks[i] print("after pass", n - end, marks)after pass 1 [1, 4, 2, 5, 8] after pass 2 [1, 2, 4, 5, 8] after pass 3 [1, 2, 4, 5, 8] after pass 4 [1, 2, 4, 5, 8]
What this code does
- Each pass pushes the largest remaining mark to the right, so 8 is already in place after the first pass.
- Printing the list after each pass is the best way to trace a sort on paper.
Example 2 · The early exit saves passes
def bubble_passes(items): items = items[:] passes = 0 while True: passes += 1 swapped = False for i in range(len(items) - 1): if items[i] > items[i + 1]: items[i], items[i + 1] = items[i + 1], items[i] swapped = True if not swapped: return passes
print(bubble_passes([1, 2, 3, 4, 5]))print(bubble_passes([5, 4, 3, 2, 1]))1 5
What this code does
- A sorted list needs one pass, just to see that nothing moves: O(n) time.
- A reversed list of 5 needs 4 passes with swaps and a fifth to confirm: the O(n squared) worst case.
The tuple swap a, b = b, a needs no temporary variable. The swapped flag stops early on a sorted list. Worst case is O(n squared) time, with O(1) extra space.
Selection sort: pick the smallest
Selection sort is a sort that repeatedly selects the smallest item of the unsorted part and swaps it into the next place of the sorted part.
Find the smallest value in the unsorted part and swap it to the front of that part. Then repeat for the rest. The front of the list grows one sorted item per round.
def selection_sort(items): for start in range(len(items) - 1): smallest = start for i in range(start + 1, len(items)): if items[i] < items[smallest]: smallest = i items[start], items[smallest] = items[smallest], items[start]
prices = [29, 10, 14, 37, 13]selection_sort(prices)print(prices)Example 3 · Selection sort makes few swaps
def selection_sort(items): swaps = 0 for start in range(len(items) - 1): smallest = start for i in range(start + 1, len(items)): if items[i] < items[smallest]: smallest = i if smallest != start: items[start], items[smallest] = items[smallest], items[start] swaps += 1 return swaps
prices = [29, 10, 14, 37, 13]print(selection_sort(prices), prices)3 [10, 13, 14, 29, 37]
What this code does
- Only 3 swaps move the five prices into place.
- Comparisons are always n(n-1)/2, but swaps are at most n - 1. That matters when writing is expensive.
It always scans the whole unsorted part, so even a sorted list costs O(n squared) comparisons. It makes at most n - 1 swaps, the fewest of the three.
Insertion sort: grow a sorted front
Insertion sort is a sort that builds a sorted front part by taking each next value and shifting larger values right until the value fits in its place.
Take the next value and slide it left past every larger value until it fits. This is how many people sort playing cards in their hand.
def insertion_sort(items): for i in range(1, len(items)): value = items[i] j = i - 1 while j >= 0 and items[j] > value: items[j + 1] = items[j] j -= 1 items[j + 1] = value
ages = [12, 11, 13, 5, 6]insertion_sort(ages)print(ages)Example 4 · Insertion sort, step by step
items = [7, 3, 5, 1]for i in range(1, len(items)): value = items[i] j = i - 1 while j >= 0 and items[j] > value: items[j + 1] = items[j] j -= 1 items[j + 1] = value print("sorted front:", items[:i + 1])sorted front: [3, 7] sorted front: [3, 5, 7] sorted front: [1, 3, 5, 7]
What this code does
- After step
i, the firsti + 1values are in order, but they are not yet the final places of the whole list. - The value being inserted is saved first, so the shifting cannot overwrite it.
Example 5 · Insertion sort loves nearly sorted data
def shifts(items): items = items[:] count = 0 for i in range(1, len(items)): value = items[i] j = i - 1 while j >= 0 and items[j] > value: items[j + 1] = items[j] j -= 1 count += 1 items[j + 1] = value return count
print(shifts([1, 2, 3, 5, 4, 6, 7, 8]))print(shifts([8, 7, 6, 5, 4, 3, 2, 1]))1 28
What this code does
- One neighbouring pair out of order costs a single shift. A fully reversed list of 8 costs 28 shifts, which is 8 * 7 / 2.
- The work is the number of pairs that are out of order, which is why nearly sorted data is fast.
Larger values shift one place right to open a gap. On an already sorted list the while never runs, so the best case is O(n). The worst case is O(n squared).
Which one, and why interviewers ask
Stable sort is a sort that keeps equal items in their original order. Insertion and bubble sort are stable; the usual selection sort is not, because its long swap can jump an item over an equal one.
Interviewers ask for one of these to see whether you can write loops without bugs and state the cost. Insertion sort is the practical one: fast on small or nearly sorted data. In real code, call sorted().
Example 6 · Stability: equal marks keep their order
students = [("Meera", 80), ("Arun", 90), ("Zoya", 80), ("Ben", 70)]for i in range(1, len(students)): current = students[i] j = i - 1 while j >= 0 and students[j][1] > current[1]: students[j + 1] = students[j] j -= 1 students[j + 1] = currentprint([name for name, mark in students])['Ben', 'Meera', 'Zoya', 'Arun']
What this code does
- Meera and Zoya both have 80. Because the test is a strict
>, Zoya stops behind Meera. - Using
>=would let Zoya jump ahead and break stability.
Example 7 · Selection sort can break stability
records = [("a", 3), ("b", 3), ("c", 1)]for start in range(len(records) - 1): smallest = start for i in range(start + 1, len(records)): if records[i][1] < records[smallest][1]: smallest = i records[start], records[smallest] = records[smallest], records[start]print([name for name, key in records])['c', 'b', 'a']
What this code does
- The first swap sends "a" to the far end, behind "b", though both have key 3.
- This is why a stable sort is needed when you sort by a second key after a first one.
Example 8 · The Python way
marks = [64, 34, 25, 12, 22]print(sorted(marks))print(marks)marks.sort(reverse=True)print(marks)[12, 22, 25, 34, 64] [64, 34, 25, 12, 22] [64, 34, 25, 22, 12]
What this code does
sorted()returns a new list and.sort()changes the list. Both are stable and take O(n log n) time.- The Collections module has a full lesson on
sorted(),sort(),reverseand stability.
Next step
Check your understanding
10 quick questions