4.3.5.1–4.3.5.2 - Bubble sort and merge sort (Python)
Learn to trace bubble passes and merge stages, implement their local operations, and explain why divide-and-conquer improves the growth of sorting time.
Bubble passes and swaps
Bubble sort repeatedly compares adjacent items and exchanges an out-of-order pair, moving a largest remaining value to the end of the unsorted region.
For ascending order, compare left to right and swap when values[i] > values[i + 1]. A pass means going through all pairs in the current unsorted region; one comparison is not a whole pass. After the first pass the last item is in its final position. The next pass can omit it.
For [8, 3, 6, 2], the first pass has three comparisons:
| Compared positions | List afterwards |
|---|---|
| 0 and 1 | 3, 8, 6, 2 |
| 1 and 2 | 3, 6, 8, 2 |
| 2 and 3 | 3, 6, 2, 8 |
The second pass ends 3, 2, 6, 8; the third ends 2, 3, 6, 8. Always use the changed list for the next comparison. Sorting one original pair independently from the others does not implement bubble sort.
Watch passes and early stopping
{"code":"def bubble_sort(values):\n for end in range(len(values) - 1, 0, -1):\n swapped = False\n for i in range(end):\n if values[i] > values[i + 1]:\n values[i], values[i + 1] = values[i + 1], values[i]\n swapped = True\n print(values)\n if not swapped:\n break\n\nvalues = [8, 3, 6, 2]\nbubble_sort(values)\nprint('Sorted:', values)","instructions":"Predict the list at the end of each pass before Run. Replace the initial list with [2, 3, 6, 8], predict/run again, and explain why the no-swap flag safely ends sorting after one pass.","files":[],"original_filename":"main.py","runtime_profile":"python-console-v1","file_mode":"fresh"}
A pass with no swaps establishes that every adjacent pair is ordered, so the whole list is sorted. The flag must reset before each pass. Worst-case comparisons grow like , giving time. Early stopping makes the already-sorted best case , but does not improve the quadratic worst case. This is why bubble sort is a particularly inefficient choice for large lists.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account