Python Tutorial
Bubble Sort
Repeatedly swap adjacent out-of-order pairs so the largest values 'bubble' to the end.
How Bubble Sort Works
Bubble sort walks the list comparing each pair of neighbors and swapping them if they are in the wrong order. After the first pass the largest element sits at the end. Repeat on the shrinking unsorted portion until no swaps are needed.
It is the simplest sort to understand but among the slowest at O(n²) — used mainly for teaching.
Basic Implementation
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(n - 1 - i): # last i items already sorted
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
# [11, 12, 22, 25, 34, 64, 90]Optimized: Stop Early
If a full pass makes no swaps, the list is already sorted. Tracking that flag makes the best case (already-sorted input) O(n).
def bubble_sort_fast(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped: # nothing moved -> done
break
return arrComplexity
| Case | Time | Notes |
|---|---|---|
| Best (sorted, optimized) | O(n) | One clean pass, no swaps |
| Average | O(n²) | |
| Worst (reverse sorted) | O(n²) | Every pair swaps |
| Space | O(1) | Sorts in place |
Bubble sort is stable (equal elements keep their relative order) and in-place.
Why It Is Rarely Used
Even the optimized version makes O(n²) comparisons on average — impractical beyond small inputs. In real Python, always use the built-in Timsort:
data = [64, 34, 25, 12]
data.sort() # in place, O(n log n)
new = sorted(data, reverse=True) # returns a new sorted listBest Practices
- Learn bubble sort for intuition, but use
sorted()/list.sort()in real code. - Add the early-exit flag whenever you must implement it.
- For nearly-sorted data, insertion sort is a better simple choice.
Try It Yourself
Exercise 1: After one full pass of bubble sort on [5, 1, 4, 2], what is the array?
Show solution
[1, 4, 2, 5] — the largest value (5) has bubbled to the end.
Exercise 2: What does the "swapped" flag optimization achieve?
Show solution
It stops early when a pass makes no swaps, giving O(n) best-case time on already-sorted data.
📘 Real-World Deep Dive
Knowing <strong>DSA Bubble Sort (algorithms & data structures)</strong> well is what turns algorithms & data structures from a curiosity into a daily tool — you'll reach for it in nearly every real project.
Real-Life Scenario
An end-to-end usage of DSA Bubble Sort that you'd actually see in a data pipeline or analytics notebook.
Real-Life Example
def bubble(xs):
n = len(xs)
for i in range(n):
for j in range(0, n - i - 1):
if xs[j] > xs[j+1]:
xs[j], xs[j+1] = xs[j+1], xs[j]
return xs
print(bubble([5, 2, 9, 1, 5, 6]))Expected Output
(see source)Common mistakes
- Off-by-one errors in binary-search: the standard idiom is
while lo <= hiwithmid = (lo + hi) // 2. - Recursive algorithms blow the stack for n > ~10⁴; convert to iterative with an explicit stack.
- Comparison algorithms (
sorted(iterable)) are stable by default in Python — surprising for Java/C++ users. - Treating DSA Bubble Sort as a black box without reading the docs — the API has subtle defaults that bite when you scale.
🚀 Performance & Best Practices
- Use
bisect.bisect_left/bisect_rightinstead of writing your own binary search. - Convert a sorted search into a tuple-access pattern with
numpy.searchsortedfor huge arrays. - Use
heapqfor priority queues instead of maintaining a sorted list manually. - When working with algorithms & data structures, prefer vectorised / batched operations over Python loops.
🧪 Try It Yourself
- Reproduce the snippet on a representative slice of your own data.
- Profile the snippet with
cProfileortimeitand find the single biggest improvement. - Generalise the snippet into a small, reusable function you can drop into future projects.