Bubble sort
Sorting by comparing neighbours and swapping them, pass after pass: the largest value rises, the inner loop bound shrinks, and a pass with no swap lets you stop.
- 26 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Bubble sort: what is it?
Show the answer
A sort that goes through the array comparing each cell with its right-hand neighbour, swaps them if they are in the wrong order, and starts over.
At the end of pass 1, the largest item is at the far right; at the end of pass 2, the second largest is in place, and so on.
What does this program print? It makes a single pass of bubble sort.
```python
t = [4, 1, 3, 2]
for j in range(len(t) - 1):
if t[j] > t[j + 1]:
t[j], t[j + 1] = t[j + 1], t[j]
print(t)`[1, 3, 2, 4][1, 2, 3, 4][1, 4, 3, 2][1, 3, 4, 2]
Show the answer
[1, 3, 2, 4]The 4 is swapped with the 1, then with the 3, then with the 2: it is carried all the way. The 3 and the 2 were never compared with each other, so a disorder is left for the next pass.
After pass 1 of bubble sort, it is the … item that is in its final place, at the far … of the array.
Show the answer
After pass 1 of bubble sort, it is the largest item that is in its final place, at the far right of the array.
A large item is carried from cell to cell at each comparison, until it meets a larger one. The very largest therefore goes all the way.
Early stop: what is it?
Show the answer
An improvement that ends the sort as soon as a full pass has made no swap, a sign that the array is sorted.
It rests on a flag reset to
Falseat the start of each pass and set toTrueat each swap. On a sorted array, a single pass is enough.