Sorting

Bubble Sort

Repeatedly walk the array comparing adjacent pairs and swapping any that are out of order. After pass k, the k largest elements are in their final positions at the end. Early-exit when a pass makes zero swaps.

Algorithm

Canonical input from the lesson spec is [5, 1, 4, 2, 8]. Three passes sort the array; pass three triggers the early exit.

adjacent swap Swap neighbouring out-of-order pairs.
early termination A pass with zero swaps means the array is already sorted.

Basic Implementation

basic.f90
Replay: real traced execution (multi-file project)
program sort_bubble
    implicit none
    integer :: arr(5) = [5, 1, 4, 2, 8]
    integer :: n, i, j, tmp
    logical :: swapped
    n = 5
    do i = 1, n - 1
        swapped = .false.
        do j = 1, n - i
            if (arr(j) > arr(j + 1)) then
                tmp = arr(j)
                arr(j) = arr(j + 1)
                arr(j + 1) = tmp
                swapped = .true.
            end if
        end do
        if (.not. swapped) exit
    end do
    print '(*(I0,1X))', arr
end program sort_bubble

  1. arr ← [5, 1, 4, 2, 8]

    2implicit none3integer :: arr(5) = [5, 1, 4, 2, 8]4integer :: n, i, j, tmp
    values this step[5, 1, 4, 2, 8]arr

  2. n ← 5

    5logical :: swapped6n = 57do i = 1, n - 1
    values this step5n[5, 1, 4, 2, 8]arr

  3. swapped ← .false.

    7do i = 1, n - 18    swapped = .false.9    do j = 1, n - i
    values this step.false.swapped

  4. arr(j) > arr(j+1) ← .true.

    9do j = 1, n - i10    if (arr(j) > arr(j + 1)) then11        tmp = arr(j)
    values this step.true.arr(j) > arr(j+1)[5, 1, 4, 2, 8]arr1j5arr(j)1arr(j+1)

  5. arr ← [1, 5, 4, 2, 8], swapped ← .true.

    12arr(j) = arr(j + 1)13arr(j + 1) = tmp14swapped = .true.
    values this step[5, 1, 4, 2, 8] → [1, 5, 4, 2, 8]arr.true.swapped

  6. arr(j) > arr(j+1) ← .true.

    9do j = 1, n - i10    if (arr(j) > arr(j + 1)) then11        tmp = arr(j)
    values this step.true.arr(j) > arr(j+1)[1, 5, 4, 2, 8]arr2j5arr(j)4arr(j+1)

  7. arr ← [1, 4, 5, 2, 8], swapped ← .true.

    12arr(j) = arr(j + 1)13arr(j + 1) = tmp14swapped = .true.
    values this step[1, 5, 4, 2, 8] → [1, 4, 5, 2, 8]arr.true.swapped

  8. arr(j) > arr(j+1) ← .true.

    9do j = 1, n - i10    if (arr(j) > arr(j + 1)) then11        tmp = arr(j)
    values this step.true.arr(j) > arr(j+1)[1, 4, 5, 2, 8]arr3j5arr(j)2arr(j+1)

  9. arr ← [1, 4, 2, 5, 8], swapped ← .true.

    12arr(j) = arr(j + 1)13arr(j + 1) = tmp14swapped = .true.
    values this step[1, 4, 5, 2, 8] → [1, 4, 2, 5, 8]arr.true.swapped

  10. arr(j) > arr(j+1) ← .false.

    9do j = 1, n - i10    if (arr(j) > arr(j + 1)) then11        tmp = arr(j)
    values this step.false.arr(j) > arr(j+1)[1, 4, 2, 5, 8]arr4j5arr(j)8arr(j+1)

  11. swapped ← .false.

    7do i = 1, n - 18    swapped = .false.9    do j = 1, n - i
    values this step.false.swapped

  12. arr(j) > arr(j+1) ← .false.

    9do j = 1, n - i10    if (arr(j) > arr(j + 1)) then11        tmp = arr(j)
    values this step.false.arr(j) > arr(j+1)[1, 4, 2, 5, 8]arr1j1arr(j)4arr(j+1)

  13. arr(j) > arr(j+1) ← .true.

    9do j = 1, n - i10    if (arr(j) > arr(j + 1)) then11        tmp = arr(j)
    values this step.true.arr(j) > arr(j+1)[1, 4, 2, 5, 8]arr2j4arr(j)2arr(j+1)

  14. arr ← [1, 2, 4, 5, 8], swapped ← .true.

    12arr(j) = arr(j + 1)13arr(j + 1) = tmp14swapped = .true.
    values this step[1, 4, 2, 5, 8] → [1, 2, 4, 5, 8]arr.true.swapped

  15. arr(j) > arr(j+1) ← .false.

    9do j = 1, n - i10    if (arr(j) > arr(j + 1)) then11        tmp = arr(j)
    values this step.false.arr(j) > arr(j+1)[1, 2, 4, 5, 8]arr3j4arr(j)5arr(j+1)

  16. swapped ← .false.

    7do i = 1, n - 18    swapped = .false.9    do j = 1, n - i
    values this step.false.swapped

  17. arr(j) > arr(j+1) ← .false.

    9do j = 1, n - i10    if (arr(j) > arr(j + 1)) then11        tmp = arr(j)
    values this step.false.arr(j) > arr(j+1)[1, 2, 4, 5, 8]arr1j1arr(j)2arr(j+1)

  18. arr(j) > arr(j+1) ← .false.

    9do j = 1, n - i10    if (arr(j) > arr(j + 1)) then11        tmp = arr(j)
    values this step.false.arr(j) > arr(j+1)[1, 2, 4, 5, 8]arr2j2arr(j)4arr(j+1)

  19. loop ← exit

    16    end do17    if (.not. swapped) exit18end do
    values this stepexitloop.false.swapped

  20. stdout ← 1 2 4 5 8

    18    end do19    print '(*(I0,1X))', arr20end program sort_bubble
    values this step1 2 4 5 8stdout[1, 2, 4, 5, 8]arr

Complexity

  • Time: O(n^2) worst and average, O(n) best with early exit
  • Space: O(1)
  • Stable: yes

Implementation notes

  • Fortran: write the two explicit loops and the swapped flag. Do not use array-section reshuffling; it would hide the comparison-and-swap mechanics the lesson is teaching.
  • The replay shows the compared pair on each frame and the post-swap array, matching the lesson spec's per-pass tables.