Bubble, insertion, selection
Use explicit passes to see how local swaps, a growing prefix, and suffix minima establish order.
Coding Patterns/Basics · B1
Sorting is a constraint decision.
Merge and quick sort
Choose predictable stable merging or in-place partitioning when quadratic passes stop fitting the input size.
Count or partition
Use bounded key ranges or a small set of values to achieve linear work without general comparison sorting.
Runnable session
Sort with a reason.
7 exercises · 49 named checks · Python 3 in your browser · saved locally
Easy16 min target
Bubble Sort Passes
Implement bubble_sort(values). Return a new ascending list without mutating values. Use adjacent swaps and stop early when a complete pass makes no swaps; do not use sorted() or list.sort().
Examples
Input [7, 3, 5, 2]
Output [2, 3, 5, 7]
Each pass bubbles the largest remaining value to the end of the unsorted region.
Input [1, 2, 3, 4]
Output [1, 2, 3, 4]
An already-sorted input finishes after one swap-free pass.
Constraints
- 0 ≤ len(values) ≤ 2,000
- Values are integers
- The input list must remain unchanged
- Stop after a pass with no swaps
Your code runs privately in the browser. Visible checks cover empty, boundary, and representative cases.
Basics coverage
Watch the referenced lesson Six algorithms. Six different invariants.
| Family | Core move | Time | Extra space | Stable |
|---|---|---|---|---|
| Bubble | Swap adjacent inversions | O(n²) | O(1) | Yes |
| Insertion | Grow a sorted prefix | O(n²) | O(1) | Yes |
| Selection | Select each suffix minimum | O(n²) | O(1) | No |
| Merge | Split, then stably merge | O(n log n) | O(n) | Yes |
| Quick | Partition around a pivot | O(n log n) avg. | O(log n) avg. | No |
| Counting | Count a bounded key range | O(n + k) | O(n + k) | Can be |
Decision referenceChoose from the constraint, not the name+
Four signals choose the proof.
Read these constraints before writing a loop. They determine the invariant and the trade-off the interviewer will probe.
Prefer merge sort or a stable insertion. In a merge, take the left item first on equality.
Quicksort trades deterministic worst-case time for compact memory and strong average performance.
A small integer range or three categories can produce linear time without general comparison sorting.
Insertion sort adapts to existing order and can finish in linear time when no shifts are needed.