DSA course menu
Bubble Sort, Selection Sort and Insertion Sort in Python
Learn the three simple O(n²) sorting algorithms with Python code, step-by-step traces and comparison counts, plus what stable sorting means and when insertion sort is actually fast.
On this page
Sorting puts items in order. Python's sorted() does it for you in O(n log n), but learning how sorting works teaches you to reason about algorithms, and the simple sorts below are interview staples.
All three are O(n²) in the worst case, sort in place with O(1) extra memory, and are easy to write.
Bubble sort#
Walk through the list comparing neighbours and swapping them if they are out of order. After each pass, the largest remaining item has "bubbled" to the end. Stop early if a pass makes no swaps.
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
print(items)
if not swapped:
break
return items
bubble_sort([5, 1, 4, 2, 8])[1, 4, 2, 5, 8]
[1, 2, 4, 5, 8]
[1, 2, 4, 5, 8]The last pass made no swaps, so the loop stopped early.
Selection sort#
Find the smallest item in the unsorted part and swap it to the front. Repeat for the rest.
def selection_sort(items):
n = len(items)
for start in range(n - 1):
smallest = start
for i in range(start + 1, n):
if items[i] < items[smallest]:
smallest = i
items[start], items[smallest] = items[smallest], items[start]
print(items)
return items
selection_sort([64, 25, 12, 22, 11])[11, 25, 12, 22, 64]
[11, 12, 25, 22, 64]
[11, 12, 22, 25, 64]
[11, 12, 22, 25, 64]Selection sort always does n(n−1)/2 comparisons, even on sorted input, but at most n − 1 swaps. That makes it useful only when writing to memory is very expensive.
Insertion sort#
Take items one at a time and insert each into its place among the items already sorted, shifting bigger ones right. This is how most people sort a hand of cards.
def insertion_sort(items):
for i in range(1, len(items)):
current = items[i]
j = i - 1
while j >= 0 and items[j] > current:
items[j + 1] = items[j] # shift right
j -= 1
items[j + 1] = current
print(items)
return items
insertion_sort([12, 11, 13, 5, 6])[11, 12, 13, 5, 6]
[11, 12, 13, 5, 6]
[5, 11, 12, 13, 6]
[5, 6, 11, 12, 13]Counting comparisons#
Each function below counts its comparisons. On already-sorted input, insertion sort (and bubble sort with early exit) do almost no work, while selection sort does the full O(n²):
import random
def bubble(items):
items, c = items[:], 0
for end in range(len(items) - 1, 0, -1):
swapped = False
for i in range(end):
c += 1
if items[i] > items[i + 1]:
items[i], items[i + 1] = items[i + 1], items[i]
swapped = True
if not swapped:
break
return items, c
def selection(items):
items, c = items[:], 0
for s in range(len(items) - 1):
m = s
for i in range(s + 1, len(items)):
c += 1
if items[i] < items[m]:
m = i
items[s], items[m] = items[m], items[s]
return items, c
def insertion(items):
items, c = items[:], 0
for i in range(1, len(items)):
cur, j = items[i], i - 1
while j >= 0:
c += 1
if items[j] <= cur:
break
items[j + 1] = items[j]
j -= 1
items[j + 1] = cur
return items, c
random.seed(1)
inputs = {
"random": random.sample(range(1000), 200),
"sorted": list(range(200)),
"reversed": list(range(200, 0, -1)),
}
for name, data in inputs.items():
counts = [f(data)[1] for f in (bubble, selection, insertion)]
assert all(f(data)[0] == sorted(data) for f in (bubble, selection, insertion))
print(f"{name:>8}: bubble {counts[0]:>5}, selection {counts[1]:>5}, insertion {counts[2]:>5}") random: bubble 19795, selection 19900, insertion 10467
sorted: bubble 199, selection 19900, insertion 199
reversed: bubble 19900, selection 19900, insertion 19900The assert line checks all three against Python's own sorted(). On nearly sorted data insertion sort is close to O(n), which is why fast library sorts (like Python's Timsort) switch to insertion sort for small or almost-sorted pieces.
Stability#
A sort is stable if items that compare equal keep their original order. It matters when sorting records by one field after another:
people = [("Asha", 25), ("Ravi", 30), ("Meera", 25), ("John", 30)]
print(sorted(people, key=lambda p: p[1]))[('Asha', 25), ('Meera', 25), ('Ravi', 30), ('John', 30)]Python's sorted is stable, so Asha stays before Meera and Ravi before John. Bubble and insertion sort are stable; selection sort is not (its long-distance swaps can jump an item over an equal one).
Common mistakes#
Practice#
Practice exercise
Modify insertion sort to sort a list of words by length, keeping words of the same length in their original order. Return a new list and leave the input unchanged.
Show hint
Copy the list first. Compare len(items[j]) > len(current) instead of the items themselves. Using > (not >=) keeps equal-length words in order.
Show solution
def sort_by_length(words):
items = words[:]
for i in range(1, len(items)):
current = items[i]
j = i - 1
while j >= 0 and len(items[j]) > len(current):
items[j + 1] = items[j]
j -= 1
items[j + 1] = current
return items
words = ["banana", "fig", "apple", "kiwi", "plum", "date"]
print(sort_by_length(words))
print(words)['fig', 'kiwi', 'plum', 'date', 'apple', 'banana']
['banana', 'fig', 'apple', 'kiwi', 'plum', 'date']"kiwi", "plum" and "date" all have 4 letters and keep their original order: the sort is stable.
Key takeaway#
Next: divide and conquer, in Merge Sort.
Finished this lesson?