Bubble Sort Algorithm in DSA Rust

Mental Model

Bubble sort repeatedly swaps adjacent items if they are in the wrong order, pushing the largest unsorted item to the end each pass.

Analogy: Imagine bubbles rising in water: the biggest bubble slowly moves up to the surface by swapping places with smaller bubbles below it.

Index: 0   1   2   3   4
Array: [5]->[3]->[8]->[4]->[2]

Dry Run Walkthrough

Input: array: [5, 3, 8, 4, 2]

Goal: Sort the array in ascending order using bubble sort

Step 1: Compare 5 and 3, swap because 5 > 3

[3] -> [5] -> [8] -> [4] -> [2]

Why: Swap to move larger number rightwards

Step 2: Compare 5 and 8, no swap because 5 < 8

[3] -> [5] -> [8] -> [4] -> [2]

Why: No swap needed, order correct

Step 3: Compare 8 and 4, swap because 8 > 4

[3] -> [5] -> [4] -> [8] -> [2]

Why: Swap to push bigger number rightwards

Step 4: Compare 8 and 2, swap because 8 > 2

[3] -> [5] -> [4] -> [2] -> [8]

Why: Largest number 8 bubbled to end

Step 5: Start next pass: compare 3 and 5, no swap

[3] -> [5] -> [4] -> [2] -> [8]

Why: First two elements in order

Step 6: Compare 5 and 4, swap because 5 > 4

[3] -> [4] -> [5] -> [2] -> [8]

Why: Swap to move bigger number rightwards

Step 7: Compare 5 and 2, swap because 5 > 2

[3] -> [4] -> [2] -> [5] -> [8]

Why: Push next largest number rightwards

Step 8: Start next pass: compare 3 and 4, no swap

[3] -> [4] -> [2] -> [5] -> [8]

Why: First two elements in order

Step 9: Compare 4 and 2, swap because 4 > 2

[3] -> [2] -> [4] -> [5] -> [8]

Why: Swap to move bigger number rightwards

Step 10: Start next pass: compare 3 and 2, swap because 3 > 2

[2] -> [3] -> [4] -> [5] -> [8]

Why: Swap to sort smaller elements

Step 11: No swaps in next pass, array is sorted

[2] -> [3] -> [4] -> [5] -> [8]

Why: Sorting complete when no swaps occur

Result:

[2] -> [3] -> [4] -> [5] -> [8]

Annotated Code

DSA Rust

fn bubble_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 0..n {
        let mut swapped = false;
        for j in 0..n - 1 - i {
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1); // swap adjacent if out of order
                swapped = true; // mark that a swap happened
            }
        }
        if !swapped {
            break; // no swaps means array is sorted
        }
    }
}

fn main() {
    let mut data = [5, 3, 8, 4, 2];
    bubble_sort(&mut data);
    for val in data.iter() {
        print!("{} ", val);
    }
    println!();
}

for i in 0..n {

outer loop controls passes over array

let mut swapped = false;

track if any swaps happen this pass

for j in 0..n - 1 - i {

inner loop compares adjacent pairs, shrinking range each pass

if arr[j] > arr[j + 1] {

check if adjacent elements are out of order

arr.swap(j, j + 1); // swap adjacent if out of order

swap to move bigger element rightwards

swapped = true; // mark that a swap happened

record that a swap occurred this pass

if !swapped { break; }

stop early if no swaps, array is sorted

Output

2 3 4 5 8 

Complexity Analysis

Time: O(n^2) because in worst case we compare and swap pairs for each element multiple times

Space: O(1) because sorting is done in place without extra storage

vs Alternative: Compared to more advanced sorts like quicksort (O(n log n)), bubble sort is slower but simpler to understand and implement

Edge Cases

empty array

function returns immediately without error

DSA Rust

let n = arr.len();

array with one element

no swaps needed, returns immediately

DSA Rust

for i in 0..n {

already sorted array

early break after first pass with no swaps

DSA Rust

if !swapped { break; }

When to Use This Pattern

When you see a problem asking to sort a small list with simple swaps and no extra space, bubble sort is a good first approach because it repeatedly pushes largest unsorted elements to the end.

Common Mistakes

Mistake: Not reducing the inner loop range each pass, causing unnecessary comparisons
Fix: Use 'n - 1 - i' as the inner loop limit to avoid checking already sorted elements

Mistake: Not breaking early when no swaps happen, causing extra passes
Fix: Add a swapped flag and break the outer loop if no swaps occur in a pass

Summary

Bubble sort repeatedly swaps adjacent out-of-order elements to sort the array.

Use it for small or nearly sorted arrays where simplicity matters more than speed.

The key insight is that each pass bubbles the largest unsorted element to its correct position.

Practice

1. What is the main idea behind the Bubble Sort algorithm?

easy

A. Select the smallest element and move it to the beginning

B. Repeatedly swap adjacent elements if they are in the wrong order

C. Divide the list into halves and sort each half separately

D. Insert each element into its correct position in a sorted sublist

Solution

1. Step 1: Understand Bubble Sort process

   Bubble Sort compares adjacent elements and swaps them if they are out of order.

2. Step 2: Compare with other sorting methods

   Other options describe different sorting algorithms like merge sort, selection sort, and insertion sort.

3. Final Answer:

   Repeatedly swap adjacent elements if they are in the wrong order -> Option B

4. Quick Check:

   Bubble Sort = swapping adjacent pairs [OK]

Hint: Bubble Sort swaps neighbors repeatedly until sorted [OK]

Common Mistakes:

• Confusing Bubble Sort with Selection Sort
• Thinking it divides the list like Merge Sort
• Assuming it inserts elements like Insertion Sort

2. Which of the following is the correct Rust syntax to swap two elements a[i] and a[i+1] in a vector a during Bubble Sort?

easy

A. std::mem::swap(a[i], a[i + 1]);

B. swap(a[i], a[i + 1]);

C. a.swap(i, i + 1);

D. a[i], a[i + 1] = a[i + 1], a[i];

Solution

1. Step 1: Identify Rust vector swap method

   Rust vectors have a built-in method swap(index1, index2) to swap elements safely.

2. Step 2: Check other options for correctness

   std::mem::swap(a[i], a[i + 1]); lacks mutable references and won't compile, swap(a[i], a[i + 1]); is invalid syntax with no such function, a[i], a[i + 1] = a[i + 1], a[i]; is invalid Python-style syntax in Rust.

3. Final Answer:

   a.swap(i, i + 1); -> Option C

4. Quick Check:

   Rust vector swap method = a.swap(i, i + 1) [OK]

Hint: Use vector.swap(i, j) to swap elements in Rust [OK]

Common Mistakes:

• Using Python or C++ style swap syntax
• Trying to swap values directly without references
• Calling std::mem::swap on vector elements incorrectly

3. What will be the output of the following Rust code snippet after applying one full pass of Bubble Sort on the vector?

let mut a = vec![4, 3, 2, 1];
for i in 0..a.len() - 1 {
    if a[i] > a[i + 1] {
        a.swap(i, i + 1);
    }
}
println!("{:?}", a);

medium

A. [3, 2, 1, 4]

B. [1, 2, 3, 4]

C. [4, 3, 2, 1]

D. [2, 3, 1, 4]

Solution

1. Step 1: Trace the single pass swaps

   Start with [4, 3, 2, 1]. Compare pairs: - 4 > 3: swap -> [3, 4, 2, 1] - 4 > 2: swap -> [3, 2, 4, 1] - 4 > 1: swap -> [3, 2, 1, 4]

2. Step 2: Final vector after one pass

   After one pass, largest element 4 bubbles to the end. Vector is [3, 2, 1, 4].

3. Final Answer:

   [3, 2, 1, 4] -> Option A

4. Quick Check:

   One pass moves largest to end = [3, 2, 1, 4] [OK]

Hint: One pass moves largest element to the end [OK]

Common Mistakes:

• Assuming full sort after one pass
• Not swapping correctly on each comparison
• Confusing indices and swapping wrong elements

4. Identify the bug in this Rust Bubble Sort code snippet and select the correct fix:

let mut a = vec![5, 1, 4, 2, 8];
for i in 0..a.len() {
    for j in 0..a.len() {
        if a[j] > a[j + 1] {
            a.swap(j, j + 1);
        }
    }
}

medium

A. Change inner loop to 0..a.len() - 1 to avoid out-of-bounds

B. Change outer loop to 0..a.len() - 1 to avoid missing last element

C. Replace a.swap(j, j + 1) with std::mem::swap(&mut a[j], &mut a[j + 1])

D. Add a break statement inside inner loop to stop early

Solution

1. Step 1: Identify out-of-bounds error

   Inner loop uses j in 0..a.len(), so j+1 can be equal to a.len(), causing panic.

2. Step 2: Fix inner loop range

   Changing inner loop to 0..a.len() - 1 prevents accessing index out of range.

3. Final Answer:

   Change inner loop to 0..a.len() - 1 to avoid out-of-bounds -> Option A

4. Quick Check:

   Inner loop must stop before last index [OK]

Hint: Inner loop must run till length-1 to avoid index error [OK]

Common Mistakes:

• Not adjusting inner loop range causing panic
• Changing outer loop instead of inner loop
• Using wrong swap method causing compile error

5. Given a vector vec![3, 0, -1, 5, 2], how many total swaps will Bubble Sort perform to fully sort the vector in ascending order?

hard

A. 4

B. 7

C. 6

D. 5

Solution

1. Step 1: Trace swaps pass by pass

   Initial: [3, 0, -1, 5, 2] Pass 1 swaps: - 3 > 0 swap -> [0, 3, -1, 5, 2] - 3 > -1 swap -> [0, -1, 3, 5, 2] - 5 > 2 swap -> [0, -1, 3, 2, 5] Total swaps: 3

2. Step 2: Continue passes and count swaps

   Pass 2: - 0 > -1 no - -1 > 3 no - 3 > 2 swap -> [0, -1, 2, 3, 5] Total swaps: 1 Pass 3: - 0 > -1 no - -1 > 2 no No swaps Pass 4: No swaps Total swaps overall = 3 + 1 + 0 + 0 = 4 (recheck)

3. Step 3: Recount carefully

   Actually, in Pass 1, 3 > 0 swap (1), 3 > -1 swap (2), 5 > 2 swap (3) Pass 2, 0 > -1 no, -1 > 3 no, 3 > 2 swap (4) Pass 3, 0 > -1 no, -1 > 2 no Pass 4 no swaps Total swaps = 4

4. Step 4: Check for missed swaps

   Pass 2 also compares 2 and 3, no swap; Pass 3 no swaps; Pass 4 no swaps. But initial count missed the swap between 3 and 2 in Pass 2, and also the swap between 3 and 2 in Pass 2 is counted once. Total swaps = 4 as per trace.

5. Step 5: Verify by counting inversions

   Count inversions in initial array: (3,0), (3,-1), (3,2), (0,-1), (5,2) Total inversions = 5 Bubble Sort swaps equal to number of inversions, so total swaps = 5

6. Final Answer:

   5 -> Option D

7. Quick Check:

   Number of swaps equals number of inversions = 5 [OK]

Hint: Count swaps each pass until no swaps remain or count inversions [OK]

Common Mistakes:

• Counting comparisons instead of swaps
• Missing swaps in later passes
• Assuming swaps equal to length minus one