Bubble Sort Algorithm in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bubble Sort on a small array

What is the output of the following Rust code after performing bubble sort on the array?

DSA Rust

fn bubble_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 0..n {
        for j in 0..n - i - 1 {
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1);
            }
        }
    }
}

fn main() {
    let mut data = [4, 2, 5, 1];
    bubble_sort(&mut data);
    println!("{:?}", data);
}

A [5, 4, 2, 1]

B [4, 2, 5, 1]

C [1, 2, 4, 5]

D [1, 2, 5, 4]

💡 Hint

Bubble sort repeatedly swaps adjacent elements if they are in the wrong order.

The bubble sort algorithm compares adjacent elements and swaps them if the left one is greater than the right one. After all passes, the array is sorted in ascending order.

🧠 Conceptual

intermediate

Number of passes in Bubble Sort

For an array of length n, how many passes does the bubble sort algorithm perform in the worst case?

A n passes

B n/2 passes

C n+1 passes

D n-1 passes

💡 Hint

Each pass places the largest unsorted element at the end.

Bubble sort performs n-1 passes because after each pass, the largest unsorted element is placed at its correct position, so only n-1 passes are needed to sort n elements.

🔧 Debug

advanced

Identify the bug in this Bubble Sort implementation

What error will this Rust bubble sort code cause when run?

DSA Rust

fn bubble_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 0..n {
        for j in 0..n - i {
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1);
            }
        }
    }
}

A Index out of bounds panic

B No error, sorts correctly

C Compilation error due to missing semicolon

D Infinite loop

💡 Hint

Check the inner loop range and the index used for swapping.

The inner loop runs from 0 to n - i, but accessing arr[j + 1] when j = n - i - 1 causes an index out of bounds panic because arr[j + 1] is out of range.

❓ Predict Output

advanced

Output after partial bubble sort passes

What is the state of the array after the first pass of bubble sort on [3, 1, 4, 2]?

DSA Rust

fn bubble_sort_pass(arr: &mut [i32]) {
    let n = arr.len();
    for j in 0..n - 1 {
        if arr[j] > arr[j + 1] {
            arr.swap(j, j + 1);
        }
    }
}

fn main() {
    let mut data = [3, 1, 4, 2];
    bubble_sort_pass(&mut data);
    println!("{:?}", data);
}

A [1, 3, 2, 4]

B [1, 2, 3, 4]

C [3, 1, 4, 2]

D [2, 3, 1, 4]

💡 Hint

One pass moves the largest element to the end.

During the first pass, adjacent elements are compared and swapped if needed. The largest element 4 moves to the end, and the array becomes [1, 3, 2, 4].

🚀 Application

expert

Optimizing Bubble Sort to stop early

Which code snippet correctly implements an optimized bubble sort that stops if no swaps occur during a pass?

A

fn bubble_sort(arr: &mut [i32]) {
    let n = arr.len();
    let mut swapped = true;
    while swapped {
        swapped = false;
        for j in 0..n - 1 {
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1);
                swapped = true;
            }
        }
    }
}

B

fn bubble_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 0..n {
        let mut swapped = false;
        for j in 0..n - i - 1 {
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1);
                swapped = true;
            }
        }
        if !swapped {
            break;
        }
    }
}

C

fn bubble_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 0..n {
        for j in 0..n - i - 1 {
            if arr[j] < arr[j + 1] {
                arr.swap(j, j + 1);
            }
        }
    }
}

D

fn bubble_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 0..n {
        let mut swapped = false;
        for j in 0..n - i - 1 {
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1);
            }
        }
        if swapped {
            break;
        }
    }
}

💡 Hint

Track if any swap happened during a pass and break if none.

Option B correctly uses a boolean flag 'swapped' to detect if any swaps occurred during a pass. If no swaps happen, the array is sorted and the loop breaks early. Option B is also correct logically but does not reduce the range of inner loop as passes progress, making it less efficient. Option B sorts in descending order, not ascending. Option B never sets swapped to true, so it never breaks early.

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