Arrays and Iteration

Reverse Array In Place (Two Pointers)

Walk two indices toward each other from the ends of the array, swapping at each step. The two-pointer pattern with the smallest possible state. The loop stops when the indices meet or cross.

Algorithm

The canonical input [1, 2, 3, 4, 5, 6, 7] reverses to [7, 6, 5, 4, 3, 2, 1] after three swaps. The middle element at index 4 (1-based) is untouched because the pointers meet there.

two pointers Indices walk toward each other and swap.

Basic Implementation

basic.f90
Replay: real traced execution (multi-file project)
program array_reverse
    implicit none
    integer :: arr(7) = [1, 2, 3, 4, 5, 6, 7]
    integer :: left, right, tmp
    left = 1
    right = 7
    do while (left < right)
        tmp = arr(left)
        arr(left) = arr(right)
        arr(right) = tmp
        left = left + 1
        right = right - 1
    end do
    print '(*(I0,1X))', arr
end program array_reverse

  1. arr ← [1, 2, 3, 4, 5, 6, 7]

    2implicit none3integer :: arr(7) = [1, 2, 3, 4, 5, 6, 7]4integer :: left, right, tmp
    values this step[1, 2, 3, 4, 5, 6, 7]arr

  2. left ← 1

    4integer :: left, right, tmp5left = 16right = 7
    values this step1left[1, 2, 3, 4, 5, 6, 7]arr

  3. right ← 7

    5left = 16right = 77do while (left < right)
    values this step7right[1, 2, 3, 4, 5, 6, 7]arr1left

  4. arr ← [7, 2, 3, 4, 5, 6, 1]

    9arr(left) = arr(right)10arr(right) = tmp11left = left + 1
    values this step[1, 2, 3, 4, 5, 6, 7] → [7, 2, 3, 4, 5, 6, 1]arr1left7right

  5. left ← 2

    10arr(right) = tmp11left = left + 112right = right - 1
    values this step1 → 2left

  6. right ← 6

    11    left = left + 112    right = right - 113end do
    values this step7 → 6right

  7. arr ← [7, 6, 3, 4, 5, 2, 1]

    9arr(left) = arr(right)10arr(right) = tmp11left = left + 1
    values this step[7, 2, 3, 4, 5, 6, 1] → [7, 6, 3, 4, 5, 2, 1]arr2left6right

  8. left ← 3

    10arr(right) = tmp11left = left + 112right = right - 1
    values this step2 → 3left

  9. right ← 5

    11    left = left + 112    right = right - 113end do
    values this step6 → 5right

  10. arr ← [7, 6, 5, 4, 3, 2, 1]

    9arr(left) = arr(right)10arr(right) = tmp11left = left + 1
    values this step[7, 6, 3, 4, 5, 2, 1] → [7, 6, 5, 4, 3, 2, 1]arr3left5right

  11. left ← 4

    10arr(right) = tmp11left = left + 112right = right - 1
    values this step3 → 4left

  12. right ← 4

    11    left = left + 112    right = right - 113end do
    values this step5 → 4right

  13. do while (left < right)

    6right = 77do while (left < right)8    tmp = arr(left)
    values this step[7, 6, 5, 4, 3, 2, 1]arr4left4right

  14. stdout ← 7 6 5 4 3 2 1

    13    end do14    print '(*(I0,1X))', arr15end program array_reverse
    values this step7 6 5 4 3 2 1stdout[7, 6, 5, 4, 3, 2, 1]arr

Complexity

  • Time: O(n)
  • Space: O(1)

Implementation notes

  • Fortran: use the explicit tmp = arr(left); arr(left) = arr(right); arr(right) = tmp triple. Avoid arr = arr(7:1:-1); it would hide the step-by-step pointer walk the lesson is teaching.
  • Replay highlights both left and right per frame plus the new array contents after each swap, matching the lesson spec.