Summary - Bubble sort
- Algorithms course
- Beginner
- Lesson 24/80
- 4 min
Implement bubble sort and print the result.
Summary - Bubble sort
In this group you learned bubble sort's logic, one pass, full sort and sorted check. Complexity is O(n^2).
Bubble sort is simple but slow. The optimized version can achieve best case O(n) by stopping when no swap occurs.
Practice Full bubble sort
Write bubble_full(arr). Sort with two loops and return. Print [1, 2, 5, 8] with print(bubble_full([5, 2, 8, 1])).
Starter code
def bubble_full(arr):
# Fully sortSample solution
def bubble_full(arr):
# Fully sort
n = len(arr)
for i in range(n):
for j in range(n - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
print(bubble_full([5, 2, 8, 1]))Expected output
[1, 2, 5, 8]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Summary - Bubble sort: match the terms
| Term | Meaning |
|---|---|
Bubble sort |
Compare neighbors |
O(n^2) |
Worst |
Swap |
Exchange |
Sorted |
O(n) best |
2 Bubble sort
Question
Bubble sort sorts ____ elements.
Answer
Bubble sort sorts adjacent elements.Explanation: adjacent is right.
3 How long does bubble sort take in the best case?
- O(n^2)
- O(n log n)
- O(1) Correct answer
- O(n)
Explanation: The best case is O(n).