Bubble Sort Algorithm in DSA Rust - Execution Trace

Concept Flow - Bubble Sort Algorithm

Start with unsorted array

↓

Compare adjacent elements

↓

If left > right?

No→Move to next pair

|Yes↓

Swap elements

↓

Reach end of array?

No→Repeat compare-swap

Yes↓

Check if any swaps done?

No→Sorted, Done

|Yes↓

Repeat entire process

Bubble Sort repeatedly compares and swaps adjacent elements if they are in the wrong order, passing through the array multiple times until no swaps are needed.

Execution Sample

DSA Rust

let mut arr = vec![5, 3, 8, 1, 2];
for i in 0..arr.len() {
  let mut swapped = false;
  for j in 0..arr.len() - 1 - i {
    if arr[j] > arr[j + 1] {
      arr.swap(j, j + 1);
      swapped = true;
    }
  }
  if !swapped {
    break;
  }
}

This code sorts the array by repeatedly swapping adjacent elements if they are out of order, with early termination if no swaps occur in a pass.

Execution Table

Step	Operation	Comparison	Swap?	Array State
1.1	Compare arr[0] and arr[1]	5 > 3	Yes	[3, 5, 8, 1, 2]
1.2	Compare arr[1] and arr[2]	5 > 8	No	[3, 5, 8, 1, 2]
1.3	Compare arr[2] and arr[3]	8 > 1	Yes	[3, 5, 1, 8, 2]
1.4	Compare arr[3] and arr[4]	8 > 2	Yes	[3, 5, 1, 2, 8]
2.1	Compare arr[0] and arr[1]	3 > 5	No	[3, 5, 1, 2, 8]
2.2	Compare arr[1] and arr[2]	5 > 1	Yes	[3, 1, 5, 2, 8]
2.3	Compare arr[2] and arr[3]	5 > 2	Yes	[3, 1, 2, 5, 8]
3.1	Compare arr[0] and arr[1]	3 > 1	Yes	[1, 3, 2, 5, 8]
3.2	Compare arr[1] and arr[2]	3 > 2	Yes	[1, 2, 3, 5, 8]
4.1	Compare arr[0] and arr[1]	1 > 2	No	[1, 2, 3, 5, 8]
Exit	No swaps in last pass	-	No	[1, 2, 3, 5, 8]

💡 No swaps done in pass 4, array is sorted

Variable Tracker

Variable	Start	After 1.1	After 1.4	After 2.3	After 3.2	After 4.1	Final
arr	[5, 3, 8, 1, 2]	[3, 5, 8, 1, 2]	[3, 5, 1, 2, 8]	[3, 1, 2, 5, 8]	[1, 2, 3, 5, 8]	[1, 2, 3, 5, 8]	[1, 2, 3, 5, 8]
swapped	false	true	true	true	true	false	false
i (pass)	0	0	0	1	2	3	3
j (index)	-	0	3	2	1	0	-

Key Moments - 3 Insights

Why do we reduce the inner loop range by 'i' each pass?

Because after each pass, the largest element settles at the end, so we don't need to compare it again. See execution_table rows 1.4, 2.3, 3.2 where the last elements are already sorted.

What happens if no swaps occur during a pass?

It means the array is sorted and we can stop early. This is shown in the exit row where no swaps happen in pass 4.

Why do we compare arr[j] and arr[j+1] instead of other pairs?

Because Bubble Sort only swaps adjacent elements to 'bubble' the largest to the end. This adjacency is key, as shown in every comparison step in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 1.3, what is the array state after the operation?

A [3, 5, 1, 8, 2]

B [3, 5, 8, 1, 2]

C [5, 3, 8, 1, 2]

D [3, 1, 5, 2, 8]

💡 Hint

Check the 'Array State' column in execution_table row 1.3

At which step does the array become fully sorted?

A After step 3.2

B After step 4.1

C After step 2.3

D After step 1.4

💡 Hint

Look at the array states in execution_table rows 3.2 and 4.1

If the initial array was already sorted, what would happen in the first pass?

A Multiple swaps would occur

B No swaps would occur and sorting stops early

C Only the last two elements would swap

D The algorithm would run all passes regardless

💡 Hint

Refer to the exit condition in execution_table where no swaps cause early stop

Concept Snapshot

Bubble Sort Algorithm:
- Repeatedly compare adjacent elements
- Swap if left element is greater
- Largest elements 'bubble' to the end each pass
- Reduce inner loop range after each pass
- Stop early if no swaps in a pass
- Simple but inefficient for large arrays

Full Transcript

Bubble Sort works by comparing each pair of adjacent elements in an array and swapping them if they are in the wrong order. This process repeats for multiple passes through the array. After each pass, the largest unsorted element moves to its correct position at the end. The inner loop reduces its range because the end elements become sorted. If a pass completes with no swaps, the array is sorted and the algorithm stops early. This method is easy to understand but not efficient for large data sets.

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