Lesson 02new · v2 format
Swap, Reverse & Shift: Moving Values in Place
Four moves — swap, reverse, shift-insert, neighbour-swap — are inside every in-place algorithm you will write.
01Why it matters & the intuition
Sorting algorithms look different on a whiteboard, but in code they reuse the same few moves. Bubble sort is neighbour-swap in a loop. Insertion sort is shift-insert in a loop. Quick sort is swap plus a write pointer. Once these four are automatic, writing any sort becomes putting familiar blocks together.
Think of it like…
Swapping two cups of tea needs a third empty cup: pour A into the empty cup, B into A, then the empty cup into B. Without it, you pour one tea over the other. Every swap in code has that third cup — Python just hides it in a, b = b, a.
02The code blocks
Each block: the template in Python and C++, a line-by-line trace (press play and watch the highlighted line and the variables), the mistakes that cost the most debugging time, and a recall drill. Do the drill without scrolling up— that’s what makes it stick.
Block 1
Swap two positions
Use it for: Every in-place sort (bubble, selection, quick, heap), reversing, partitioning, permutations.
1 · The template
tmp = a[i]
a[i] = a[j]
a[j] = tmp
# Python shortcut: a[i], a[j] = a[j], a[i]2 · Watch it run, line by line
▶tmp = a[i]2a[i] = a[j]3a[j] = tmp4# Python shortcut: a[i], a[j] = a[j], a[i]
Variables
- i
- 0
- j
- 2
- tmp
- None
3 · Classic mistakes
a[i] = a[j] a[j] = a[i]After the first line the old a[i] is gone, so both slots end up equal.swap(x, y) that swaps its own parametersPython ints and C++ pass-by-value copy the numbers — swap the array slots, or use references (int& x) in C++.
4 · Recall it without looking
tmp = a[i]
a[i] = a[j]
a[j] = Block 2
Reverse with two ends
Use it for: Reverse an array or string in place, palindromes, rotate-by-k (three reversals).
1 · The template
l, r = 0, len(a) - 1
while l < r:
a[l], a[r] = a[r], a[l]
l += 1
r -= 12 · Watch it run, line by line
▶l, r = 0, len(a) - 12while l < r:3a[l], a[r] = a[r], a[l]4l += 15r -= 1
Variables
- l
- 0
- r
- 4
3 · Classic mistakes
for i in range(len(a)): swap(a[i], a[n - 1 - i])Swaps every pair twice, undoing the reversal. Stop at the middle.Forgetting r -= 1Only l moves, so you swap wrong pairs and eventually cross the middle.
4 · Recall it without looking
l, r = 0, len(a) - 1
while :
a[l], a[r] = a[r], a[l]
l += 1
r 1Block 3
Shift right, then insert
Use it for: Insertion sort's inner loop, inserting into a sorted array, making room at a position.
1 · The template
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key2 · Watch it run, line by line
▶key = a[i]2j = i - 13while j >= 0 and a[j] > key:4a[j + 1] = a[j]5j -= 16a[j + 1] = key
Variables
- i
- 3
- key
- 3
3 · Classic mistakes
a[j] = key (after the loop)When the loop stops, a[j] is the element that is ≤ key — the gap is at j + 1.while a[j] > key and j >= 0:When j reaches −1, Python silently reads a[-1] (the last element!) instead of stopping. Guard first.
4 · Recall it without looking
key = a[i]
j = i - 1
while and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[] = keyBlock 4
Compare & swap neighbours (one pass)
Use it for: Bubble sort, 'push the max to the end', checking and fixing local order.
1 · The template
for i in range(len(a) - 1):
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]2 · Watch it run, line by line
▶for i in range(len(a) - 1):2if a[i] > a[i + 1]:3a[i], a[i + 1] = a[i + 1], a[i]
Variables
- i
- 0
3 · Classic mistakes
for i in range(len(a)):The neighbour a[i + 1] is out of range on the last step.if a[i] >= a[i + 1]:Still sorts, but swaps equal values needlessly and loses stability.
4 · Recall it without looking
for i in range():
if a[i] a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]03Key ideas
A swap is three assignments
tmp = a[i]; a[i] = a[j]; a[j] = tmp. Python's a[i], a[j] = a[j], a[i] and C++'s std::swap do the same thing behind the scenes.
Two pointers meeting in the middle
Start l at the front and r at the back, act on the pair, move both inward, stop when l >= r. You'll reuse this for reversing, palindromes and pair sums.
Shifting is cheaper than swapping
Insertion sort doesn't swap the key down step by step. It copies bigger elements one slot right, then writes the key once into the gap.
Trace with a tiny input
Before running code, trace it by hand on 3–5 elements, writing down the variables after each line. That is exactly what the tracer below does — copy the habit.
04Cheat sheet
Every block from this lesson on one screen. Keep it open while you do the lab — then try the lab again without it.
# swap
a[i], a[j] = a[j], a[i]
# reverse in place
l, r = 0, len(a) - 1
while l < r:
a[l], a[r] = a[r], a[l]
l += 1
r -= 1
# shift right, then insert key (insertion step)
key, j = a[i], i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
# one bubble pass
for i in range(len(a) - 1):
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]05Complexity
| Move | Cost | Extra space |
|---|---|---|
| Swap | O(1) | O(1) |
| Reverse n items | n/2 swaps → O(n) | O(1) |
| Shift-insert at position i | up to i moves → O(n) | O(1) |
| One bubble pass | n − 1 compares → O(n) | O(1) |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Reverse a segment
Reverse only the part of the array from index l to index r (both inclusive), in place, and return the array. Don't use slicing or built-in reverse — use the two-ends block.