Bubble Sort Algorithm in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to swap two elements in the array.

DSA Rust

if arr[j] > arr[j + 1] {
    let temp = arr[j];
    arr[j] = arr[j [1] 1];
    arr[j + 1] = temp;
}

Drag options to blanks, or click blank then click option'

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using '-' instead of '+' causes index errors.

Using '*' or '/' is not valid for indexing.

We add 1 to j to access the next element for swapping.

2fill in blank

medium

Complete the code to run the outer loop for bubble sort.

DSA Rust

for i in 0..arr.len() [1] 1 {
    // inner loop
}

Drag options to blanks, or click blank then click option'

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' causes the loop to run too many times.

Using '*' or '/' is invalid for loop ranges.

We subtract 1 because the last element is already sorted after each pass.

3fill in blank

hard

Fix the error in the inner loop range to avoid index out of bounds.

DSA Rust

for j in 0..arr.len() [1] i [2] 1 {
    if arr[j] > arr[j + 1] {
        arr.swap(j, j + 1);
    }
}

Drag options to blanks, or click blank then click option'

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' instead of '-' causes index errors.

Using '*' or '/' is invalid for loop ranges.

The inner loop runs until length minus i minus 1 to avoid comparing beyond the sorted part.

4fill in blank

hard

Fill both blanks to complete the bubble sort function header and return type.

DSA Rust

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

Drag options to blanks, or click blank then click option'

AVec<i32>

B-

Ci32

Dbool

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect return types like i32 or bool.

Using wrong loop range operators.

The function returns a vector of i32 and the loop runs until n minus 1.

5fill in blank

hard

Fill all three blanks to complete the bubble sort call and print the sorted array.

DSA Rust

fn main() {
    let arr = vec![64, 34, 25, 12, 22, 11, 90];
    let sorted_arr = bubble_sort([1]);
    println!("Sorted array: {:?}", [2]);
    for num in [3] {
        print!("{} ", num);
    }
}

Drag options to blanks, or click blank then click option'

Aarr

Bsorted_arr

Csorted_arr.iter()

Darr.iter()

Attempts:

3 left

💡 Hint

Common Mistakes

Passing sorted_arr to bubble_sort causes infinite recursion.

Iterating over the original array instead of the sorted one.

We pass 'arr' to bubble_sort, print 'sorted_arr', and iterate over 'sorted_arr.iter()' to print elements.

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