# Bubble Sort Algorithm with Swap Optimization

- **Track:** Cambridge IGCSE™ Computer Science (0478 / 0984) (CAMBRIDGE IGCSE 0478)
- **Module:** Section 7: Algorithm Design & Problem-Solving
- **Estimated Duration:** 20 minutes
- **Access:** Open Theory (All-Access for Interactive IDE & Autotests)

---

## Theory & Conceptual Background

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

```text
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:

```pseudocode
// 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:

```pseudocode
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.

---

## Interactive Exercises & Autotest Specifications

### Exercise 1: Exam-Style Check: Bubble Sort Swap Mechanism & Variable Loss (Multiple choice, 25 XP)

**Instructions:**
Why is a third variable (such as `Temp`) strictly required when swapping two array values `Array[i]` and `Array[i + 1]` in Cambridge pseudocode?

**Options:**
- **A**: Without a temporary variable, copying Array[i + 1] directly into Array[i] permanently overwrites and destroys the original value of Array[i].
- **B**: Because arrays cannot hold variables of the same data type without an intermediary.
- **C**: Temp is used as a Boolean flag to count how many comparisons were executed.
- **D**: Using Temp allows the microprocessor to execute the swap in zero clock cycles.


**Autotest Expectations:**
- **Need for temporary variable in swap explained**: `selection_match` -> Expected: `opt_loss`

### Exercise 2: Exam-Style Question: Order the Classic Swap Sequence (Fill in blank, 35 XP)

**Instructions:**
Complete the 3-step swap sequence to swap `Data[j]` and `Data[j + 1]` into ascending order when `Data[j] > Data[j + 1]`:

```pseudocode
Temp <- [blank_1]
Data[j] <- [blank_2]
[blank_3] <- Temp
```


**Starter Code:**
```text
{"template":"Temp <- [blank_1]\nData[j] <- [blank_2]\n[blank_3] <- Temp","word_bank":["Data[j]","Data[j + 1]","Data[j - 1]","Temp","Data[1]"],"prompt":"Exam-Style Question: Order the Classic Swap Sequence","blanks":[{"id":"blank_1"},{"id":"blank_2"},{"id":"blank_3"}]}
```

**Autotest Expectations:**
- **Data[j] stored in Temp**: `text_exact` -> Expected: `Data[j]`
- **Data[j + 1] copied to Data[j]**: `text_exact` -> Expected: `Data[j + 1]`
- **Temp copied to Data[j + 1]**: `text_exact` -> Expected: `Data[j + 1]`

### Exercise 3: Independent Practice: Complete sorting (Pseudocode, 30 XP)

**Instructions:**
Read five integers. Sort them into ascending order using bubble sort and output each sorted item on its own line. Include repeated and negative values when testing.

Write a complete program. Read inputs in the stated order. Output only the requested results, one per line, without input prompts. Test with your own values before submitting.


**Starter Code:**
```text
// Plan your solution, then write your program.

```

**Autotest Expectations:**
- **Reverse order**: `test_case` -> Expected: `{&quot;inputs&quot;:[5,4,3,2,1],&quot;output&quot;:&quot;1\n2\n3\n4\n5&quot;}`
- **Duplicates and negatives**: `test_case` -> Expected: `{&quot;inputs&quot;:[3,-1,3,0,-2],&quot;output&quot;:&quot;-2\n-1\n0\n3\n3&quot;}`
- **Already sorted**: `test_case` -> Expected: `{&quot;inputs&quot;:[1,2,3,4,5],&quot;output&quot;:&quot;1\n2\n3\n4\n5&quot;}`