Bubble Sort Algorithm with Swap Optimization

The Bubble Sort is a comparison-based sorting algorithm. It repeatedly steps through a one-dimensional array, compares pairs of adjacent elements, and swaps them if they are in the wrong order (e.g. Array[i] > Array[i + 1] for ascending order).

1. How Bubble Sort Operates

Initial:   [ 35,  12,  68,  24 ]
Compare 1: (35 > 12) -> Swap!   -> [ 12,  35,  68,  24 ]
Compare 2: (35 > 68) -> No swap -> [ 12,  35,  68,  24 ]
Compare 3: (68 > 24) -> Swap!   -> [ 12,  35,  24,  68 ]

At the end of Pass 1, the largest value (68) has "bubbled up" to the final position in the array.

Why Pass Length is $N - 1$:

If an array has $N$ elements (e.g., indices $1$ to $5$), the loop comparing Array[i] and Array[i + 1] must run from $i = 1$ to $i = N - 1$ ($1$ to $4$). Exam Warning: Running the loop to $N$ causes an Index Out of Bounds runtime error when the code attempts to evaluate Array[N + 1].

2. The Three-Step Swap Routine

For a swap using separate assignment statements, preserve the first value in a temporary variable (Temp) before overwriting it:

// Swapping Array[i] and Array[i + 1]
Temp <- Array[i]            // 1. Safeguard value of first cell
Array[i] <- Array[i + 1]    // 2. Overwrite first cell with second cell
Array[i + 1] <- Temp        // 3. Move safeguarded value into second cell

If step 1 is skipped and Array[i] <- Array[i + 1] is executed immediately, the original value in Array[i] is permanently erased from memory.

3. Early Termination Optimization (Swapped Flag)

A standard bubble sort will execute $N - 1$ passes even if the array becomes sorted early. Adding a Boolean flag enables the algorithm to stop as soon as sorting is complete:

REPEAT
    Swapped <- FALSE
    FOR i <- 1 TO 4
        IF List[i] > List[i + 1] THEN
            Temp <- List[i]
            List[i] <- List[i + 1]
            List[i + 1] <- Temp
            Swapped <- TRUE
        ENDIF
    NEXT i
UNTIL Swapped = FALSE

If a complete pass executes and Swapped remains FALSE, no adjacent inversions occurred: the array is completely sorted, saving significant processing time.