Why Bubble Sort Algorithm in DSA Rust?

The Big Idea

Discover how a simple swapping trick can turn chaos into order, step by step!

The Scenario

Imagine you have a messy stack of books on your desk. You want to arrange them from smallest to largest by height. Doing this by guessing and swapping randomly takes a lot of time and mistakes.

The Problem

Trying to sort items by hand without a clear method is slow and confusing. You might miss some books or swap the wrong ones, making the pile even messier.

The Solution

Bubble Sort helps by comparing pairs of items step-by-step and swapping them if they are in the wrong order. This way, the biggest items "bubble" to the end, making sorting simple and organized.

Before vs After

✗ Before

let mut numbers = vec![5, 3, 8, 4];
numbers.sort(); // No clear steps shown

✓ After

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

What It Enables

It makes sorting easy to understand and implement, even for beginners, by breaking the task into simple repeated steps.

Real Life Example

Sorting a list of student scores from lowest to highest so the teacher can quickly see who needs help.

Key Takeaways

Manual sorting is slow and error-prone.

Bubble Sort swaps items step-by-step to organize data.

This method is simple and great for learning sorting basics.

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