A
AiTechWorlds
AiTechWorlds
Imagine you've just been dealt a hand of playing cards and you want to arrange them in order.
You try Method 1: Scan through your entire hand, find the smallest card, and move it to the leftmost position. Then scan the remaining cards, find the next smallest, and move it to the second position. Repeat until done. This is Selection Sort.
You try Method 2: Look at the first two cards. If they're out of order, swap them. Then look at the second and third. Swap if needed. Keep going until you reach the end. The largest card has now "bubbled" to the end. Repeat for the remaining unsorted portion. This is Bubble Sort.
Both methods are simple, intuitive, and — importantly — slow for large inputs. But they teach foundational concepts that appear in every subsequent sorting algorithm.
On each pass through the array, compare adjacent elements and swap them if they're in the wrong order. After each full pass, the largest unsorted element has "bubbled" to its correct position at the end.
Visual example on [64, 34, 25, 12, 22, 11, 90]:
Initial: [64, 34, 25, 12, 22, 11, 90]
Pass 1:
64 > 34 → swap: [34, 64, 25, 12, 22, 11, 90]
64 > 25 → swap: [34, 25, 64, 12, 22, 11, 90]
64 > 12 → swap: [34, 25, 12, 64, 22, 11, 90]
64 > 22 → swap: [34, 25, 12, 22, 64, 11, 90]
64 > 11 → swap: [34, 25, 12, 22, 11, 64, 90]
64 < 90 → keep: [34, 25, 12, 22, 11, 64, 90] ← 90 in place
Pass 2:
34 > 25 → swap: [25, 34, 12, 22, 11, 64, 90]
34 > 12 → swap: [25, 12, 34, 22, 11, 64, 90]
34 > 22 → swap: [25, 12, 22, 34, 11, 64, 90]
34 > 11 → swap: [25, 12, 22, 11, 34, 64, 90] ← 64 in place
... (continues until sorted)
def bubble_sort(arr):
n = len(arr)
for i in range(n): # n passes total
for j in range(0, n - i - 1): # shrink range each pass
if arr[j] > arr[j + 1]: # compare adjacent pair
arr[j], arr[j + 1] = arr[j + 1], arr[j] # swap
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(arr))
# Output: [11, 12, 22, 25, 34, 64, 90]
def bubble_sort_optimized(arr):
n = len(arr)
for i in range(n):
swapped = False # track if any swap occurred
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped: # no swaps = already sorted
print(f"Early exit after pass {i+1}")
break
return arr
arr = [1, 2, 3, 5, 4] # nearly sorted
print(bubble_sort_optimized(arr))
# Early exit after pass 1
# Output: [1, 2, 3, 4, 5]
On an already-sorted array, the optimized version runs in O(n) — just one pass to confirm nothing needs swapping.
| Case | Time | Why |
|---|---|---|
| Best | O(n) | Already sorted — one pass, no swaps, early exit |
| Average | O(n²) | Random data needs ~n²/2 comparisons |
| Worst | O(n²) | Reverse sorted — maximum swaps every pass |
| Space | O(1) | Sorts in-place, only uses swap variables |
Divide the array into two sections: sorted (left) and unsorted (right). On each step, find the minimum element in the unsorted section and move it to the end of the sorted section.
Visual example on [64, 25, 12, 22, 11]:
Initial: [64, 25, 12, 22, 11]
^sorted^ ^unsorted^
Pass 1: min=11 at index 4, swap with index 0
[11, 25, 12, 22, 64]
^--^ sorted
Pass 2: min=12 at index 2, swap with index 1
[11, 12, 25, 22, 64]
^-----^ sorted
Pass 3: min=22 at index 3, swap with index 2
[11, 12, 22, 25, 64]
^--------^ sorted
Pass 4: min=25 at index 3, already in place
[11, 12, 22, 25, 64]
^-----------^ sorted
Done! [11, 12, 22, 25, 64]
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i # assume first unsorted is min
for j in range(i + 1, n):
if arr[j] < arr[min_idx]: # found a smaller element
min_idx = j # update min index
arr[i], arr[min_idx] = arr[min_idx], arr[i] # swap min to front
print(f"Pass {i+1}: {arr}")
return arr
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
Output:
Pass 1: [11, 25, 12, 22, 64]
Pass 2: [11, 12, 25, 22, 64]
Pass 3: [11, 12, 22, 25, 64]
Pass 4: [11, 12, 22, 25, 64]
Pass 5: [11, 12, 22, 25, 64]
| Case | Time | Why |
|---|---|---|
| Best | O(n²) | Still scans entire unsorted region every pass |
| Average | O(n²) | Same regardless of input order |
| Worst | O(n²) | Same |
| Space | O(1) | In-place |
Key insight: Selection sort makes the minimum number of swaps — at most n-1. This matters when swapping is expensive (e.g., writing to a slow storage device).
| Property | Bubble Sort | Selection Sort |
|---|---|---|
| Best case | O(n) with optimization | O(n²) always |
| Average case | O(n²) | O(n²) |
| Worst case | O(n²) | O(n²) |
| Space | O(1) | O(1) |
| Stable? | Yes | No (equal elements may reorder) |
| Swaps | O(n²) in worst case | O(n) — at most n-1 swaps |
| Comparisons | O(n²) | Always exactly n(n-1)/2 |
| Adaptive? | Yes (optimized version) | No |
Stable means equal elements maintain their original relative order after sorting. Bubble sort is stable; selection sort is not.
You might wonder: if both are O(n²), why learn them?
Legitimate use cases:
Very small arrays (n < 20): The overhead of complex algorithms like merge sort doesn't pay off. For tiny inputs, simple is fast.
Nearly sorted data: Optimized bubble sort runs in O(n) — faster than merge sort's guaranteed O(n log n) minimum.
Memory-constrained environments: Both use O(1) extra space. Merge sort requires O(n).
Selection sort for minimum writes: When writing data is expensive (e.g., EEPROM with limited write cycles), selection sort's O(n) swaps are valuable.
Educational foundation: Understanding these algorithms builds the intuition for every sorting algorithm that follows.
Even though production code never uses bubble sort on large datasets, these algorithms teach:
Python's list.sort() uses Timsort — a sophisticated hybrid. But Timsort's creators needed to deeply understand the algorithms it replaced.
Next lesson: Insertion Sort — the algorithm that beats both of these for nearly sorted data.
Get this course's notes on Telegram!
Free cheat sheets, summaries & practice exercises