Swap the two misplaced values
Updated
After L found a right-side value and R found a left-side value, swap a[L] and a[R]. Then L++ and R-- and hunt again.
What to focus on
The swap places both offenders onto the correct sides. Do not swap if L ≥ R. One swap does not finish the partition unless they then cross.
Worked examples
zero/nonzero
a = [0, 1, 0, 9], L=1 R=2- 1 should be right, 0 should be left
- swap
- a = [0, 0, 1, 9]
Result: then L=2 R=1, cross
odd/even
a = [4, 1, 9, 2], L=1 R=3, evens left- 1 odd, 2 even
- swap
- a = [4, 2, 9, 1]
Result: L=2 R=2 next hunt
around 4
a = [9, 1, 4], L=0 R=1, <4 left- 9 should be right, 1 should be left
- swap
- a = [1, 9, 4]
Result: L=1 R=0, cross
Try it
Write swapMisplaced(a, L, R). a is an array of integers. L is the left index of a right-side offender. R is the right index of a left-side offender. L < R. Swap, then L++ and R--. Print a after each swap. Return nothing. Trace [0, 1, 0, 9] at L=1 R=2 and [4, 1, 9, 2] at L=1 R=3.
a has length ≥ 2. L < R. a[L] is a right-side offender and a[R] is a left-side offender.