Bubble sort idea
- Algorithms course
- Beginner
- Lesson 21/80
- 4 min
Compare neighbours, swap, bubble the largest to the end.
Bubble sort logic
Bubble sort sorts an array by comparing adjacent elements and swapping them if they are in the wrong order. This is repeated to the end of the array.
On each pass, the largest element 'bubbles up' to the end of the array. The name comes from this bubbling motion.
One pass
In one pass, you scan the array from start to end and check each adjacent pair. If their order is wrong, swap with arr[j], arr[j+1] = arr[j+1], arr[j].
At the end of a pass, the largest element has reached its final position at the end. The pass is repeated for the remaining elements.
Practice One pass
Write bubble_one_pass(arr). Compare neighbors, swap if wrong order. Print [1, 2, 3] with print(bubble_one_pass([3, 1, 2])).
Starter code
def bubble_one_pass(arr):
# Do one passSample solution
def bubble_one_pass(arr):
# Do one pass
n = len(arr)
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_one_pass([3, 1, 2]))Expected output
[1, 2, 3]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 How does bubble sort work?
- Uses hashing
- Splits the array in half
- Finds the minimum
- Compares neighbors and swaps Correct answer
Explanation: Bubble sort compares neighbors and swaps.
2 Swapping
Swap two elements: arr[j], arr[j+1] = arr[j+1], ____Swap two elements: arr[j], arr[j+1] = arr[j+1], arr[j]Explanation: arr[j] is right.
3 Bubble sort idea: match the terms
| Term | Meaning |
|---|---|
Bubble sort |
Compare neighbors |
Pass |
Start to end |
Swap |
Exchange |
Largest |
Goes to end |