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.

Basic Implementation

basic.f90 
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

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.
adjacent swap Swap neighbouring out-of-order pairs.
early termination A pass with zero swaps means the array is already sorted.