One pass
- Algorithms course
- Beginner
- Lesson 22/80
- 4 min
Learn one pass over neighbour pairs.
Full sorting
Full bubble sort requires n-1 passes. Each pass places one element in its correct position, gradually sorting the array.
After each pass, the unsorted portion shrinks by one element. After the last pass, the array is fully sorted.
Complexity
Bubble sort's complexity is O(n^2). There are two nested loops: the outer runs n-1 times, the inner runs a decreasing number each time.
The best case (already sorted array) is O(n) because no swaps happen in one pass. However, it is generally considered O(n^2).
Practice Bubble sort
Write bubble_sort(arr). Fully sort and return the array. Print [1, 1, 3, 4, 5] with print(bubble_sort([3, 1, 4, 1, 5])).
Starter code
def bubble_sort(arr):
# Sort the arraySample solution
def bubble_sort(arr):
# Sort the array
n = len(arr)
for i in range(n - 1):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
print(bubble_sort([3, 1, 4, 1, 5]))Expected output
[1, 1, 3, 4, 5]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Pass count
For n elements, ____ passes are needed.For n elements, n - 1 passes are needed.Explanation: n - 1 is right.
2 One pass: match the terms
| Term | Meaning |
|---|---|
Bubble sort |
O(n^2) |
Pass |
n-1 times |
Swap |
Exchange |
Sorted |
O(n) best |
3 What is bubble sort's complexity?
- O(n log n) Correct answer
- O(n)
- O(1)
- O(n^2)
Explanation: Bubble sort is O(n^2).