Bubble Sort Algorithm in DSA Javascript - Execution Trace

Concept Flow - Bubble Sort Algorithm

Start with array

↓

Compare adjacent elements

↓

If left > right?

No→Move to next pair

|Yes↓

Swap elements

↓

Reach end of array?

No→Repeat compare-swap

Yes↓

Reduce array length by 1

↓

Is array length > 1?

Yes→Repeat passes

No↓

Sorted array

Bubble Sort repeatedly compares and swaps adjacent elements, pushing the largest unsorted element to the end each pass, until the array is sorted.

Execution Sample

DSA Javascript

const arr = [5, 3, 8, 1, 2];
for (let i = 0; i < arr.length - 1; i++) {
  let swapped = false;
  for (let j = 0; j < arr.length - 1 - i; j++) {
    if (arr[j] > arr[j + 1]) {
      [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      swapped = true;
    }
  }
  if (!swapped) {
    break;
  }
}

This code sorts the array by repeatedly swapping adjacent elements if they are in the wrong order.

Execution Table

Step	Operation	Comparison	Swap?	Array State
1	Compare arr[0] and arr[1]	5 > 3	Yes	[3, 5, 8, 1, 2]
2	Compare arr[1] and arr[2]	5 > 8	No	[3, 5, 8, 1, 2]
3	Compare arr[2] and arr[3]	8 > 1	Yes	[3, 5, 1, 8, 2]
4	Compare arr[3] and arr[4]	8 > 2	Yes	[3, 5, 1, 2, 8]
5	Compare arr[0] and arr[1]	3 > 5	No	[3, 5, 1, 2, 8]
6	Compare arr[1] and arr[2]	5 > 1	Yes	[3, 1, 5, 2, 8]
7	Compare arr[2] and arr[3]	5 > 2	Yes	[3, 1, 2, 5, 8]
8	Compare arr[0] and arr[1]	3 > 1	Yes	[1, 3, 2, 5, 8]
9	Compare arr[1] and arr[2]	3 > 2	Yes	[1, 2, 3, 5, 8]
10	Compare arr[0] and arr[1]	1 > 2	No	[1, 2, 3, 5, 8]
11	No more comparisons, array sorted	-	No	[1, 2, 3, 5, 8]

💡 All passes completed, no swaps needed, array is sorted

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 7	After Step 9	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]
i (pass)	0	0	0	1	2	3
j (index)	0	3	3	2	1	-

Key Moments - 3 Insights

Why do we reduce the inner loop length 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 4 and 7 where the last elements are already sorted.

Why do we swap only when the left element is greater than the right?

Swapping only when left > right ensures the larger elements move right, sorting the array ascendingly. This is shown in execution_table rows 1, 3, 4 where swaps happen only if left > right.

What stops the algorithm from running forever?

The outer loop runs a fixed number of passes (array length - 1). Also, when no swaps happen in a pass, the array is sorted and the algorithm stops, as in execution_table row 11.

Visual Quiz - 3 Questions

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

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

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

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

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

💡 Hint

Check the 'Array State' column in execution_table row 4

At which step does the algorithm first swap the elements 3 and 1?

A Step 8

B Step 6

C Step 9

D Step 2

💡 Hint

Look for the comparison '3 > 1' with a swap in execution_table

If the array was already sorted, how would the execution_table change?

A All comparisons would result in swaps

B No swaps would occur, and the algorithm would stop early

C The array state would change after every step

D The algorithm would run infinitely

💡 Hint

Refer to the exit_note and step 11 where no swaps mean sorted array

Concept Snapshot

Bubble Sort Algorithm:
- Repeatedly compare adjacent elements
- Swap if left element is greater
- Largest unsorted element moves to end each pass
- Reduce inner loop length each pass
- Stop when no swaps or passes complete

Full Transcript

Bubble Sort works by comparing pairs of adjacent elements in an array. If the left element is bigger, they swap places. This pushes the largest unsorted element to the end of the array each pass. After each pass, the algorithm reduces the number of comparisons because the end elements are sorted. The process repeats until no swaps are needed, meaning the array is sorted. The execution table shows each comparison and swap step, tracking how the array changes. Key moments include understanding why the inner loop shrinks and why swaps only happen when the left element is bigger. The algorithm stops after enough passes or when the array is sorted early.

Practice

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

easy

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

B. Divide the array into halves and sort each half separately

C. Select the smallest element and place it at the beginning

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

Solution

1. Step 1: Understand Bubble Sort mechanism

   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 algorithms: selection sort (A), divide and conquer (B), insertion sort (D).

3. Final Answer:

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

4. Quick Check:

   Bubble Sort = swapping adjacent pairs [OK]

Hint: Bubble Sort swaps neighbors repeatedly to sort [OK]

Common Mistakes:

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

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

easy

A. arr[i] = arr[i+1]; arr[i+1] = arr[i];

B. arr[i], arr[i+1] = arr[i+1], arr[i];

C. swap(arr[i], arr[i+1]);

D. let temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp;

Solution

1. Step 1: Understand JavaScript swapping

   JavaScript does not support tuple unpacking; use a temporary variable to swap.

2. Step 2: Analyze each option

   let temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; uses a temp variable correctly. arr[i], arr[i+1] = arr[i+1], arr[i]; is Python syntax, invalid in JS. swap(arr[i], arr[i+1]); calls undefined function. arr[i] = arr[i+1]; arr[i+1] = arr[i]; overwrites values incorrectly.

3. Final Answer:

   let temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; -> Option D

4. Quick Check:

   Use temp variable to swap in JS [OK]

Hint: Use temp variable to swap in JavaScript [OK]

Common Mistakes:

• Using Python-style tuple swap in JavaScript
• Calling undefined swap function
• Overwriting values without temp variable

3. What will be the output of the following JavaScript code snippet?

let arr = [4, 2, 3];
for(let i = 0; i < arr.length - 1; i++) {
  if(arr[i] > arr[i+1]) {
    let temp = arr[i];
    arr[i] = arr[i+1];
    arr[i+1] = temp;
  }
}
console.log(arr);

medium

A. [2, 4, 3]

B. [2, 3, 4]

C. [4, 2, 3]

D. [3, 2, 4]

Solution

1. Step 1: Trace the single pass of the loop

   Loop runs i=0 to 1. At i=0: 4 > 2, swap -> arr = [2,4,3]. At i=1: 4 > 3, swap -> arr = [2,3,4].

2. Step 2: Check loop range carefully

   The loop runs only once over the array (i from 0 to length-2). So swaps happen at i=0 and i=1.

3. Final Answer:

   [2, 4, 3] -> Option A

4. Quick Check:

   One pass swaps neighbors to partially sort [OK]

Hint: Trace each swap carefully for one loop pass [OK]

Common Mistakes:

• Assuming full sort after one pass
• Ignoring second swap at i=1
• Confusing array indices

4. Identify the error in this Bubble Sort code snippet and choose the correct fix:

function bubbleSort(arr) {
  for(let i = 0; i < arr.length; i++) {
    for(let j = 0; j < arr.length; j++) {
      if(arr[j] > arr[j+1]) {
        let temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
  return arr;
}

medium

A. Remove the inner loop completely

B. Change outer loop to run from i = 1 to arr.length

C. Change inner loop condition to j < arr.length - i - 1

D. Add a check to skip swapping equal elements

Solution

1. Step 1: Analyze inner loop range

   Inner loop runs till j < arr.length, so arr[j+1] can be undefined at last index causing error.

2. Step 2: Fix inner loop to avoid out-of-bound access

   Changing condition to j < arr.length - i - 1 prevents accessing beyond array length and optimizes sorting.

3. Final Answer:

   Change inner loop condition to j < arr.length - i - 1 -> Option C

4. Quick Check:

   Inner loop must avoid out-of-bound index [OK]

Hint: Inner loop stops earlier each pass to avoid overflow [OK]

Common Mistakes:

• Ignoring array boundary causing undefined access
• Changing outer loop incorrectly
• Removing inner loop breaks sorting

5. Given the array [5, 1, 4, 2, 8], how many total swaps will Bubble Sort perform to fully sort it in ascending order?

hard

A. 4

B. 6

C. 5

D. 7

Solution

1. Step 1: Perform Bubble Sort passes and count swaps

   Pass 1 swaps: (5,1), (5,4), (5,2) -> 3 swaps (5 and 8 no swap).

2. Step 2: Continue passes counting swaps

   Pass 2 swaps: (4,2) -> 1 swap. Pass 3 swaps: (4,3) none here but actually (2,3) no swap, but we need to check carefully. Actually, pass 3 swaps: (2,3) no swap, pass 4 no swaps. Total swaps: 3 + 1 + 2 = 6.

3. Step 3: Verify total swaps

   Counting carefully, total swaps are 6, so 6.

4. Final Answer:

   6 -> Option B

5. Quick Check:

   Count swaps each pass carefully [OK]

Hint: Count swaps pass by pass to avoid missing any [OK]

Common Mistakes:

• Assuming swaps equal to array length
• Counting comparisons instead of swaps
• Missing repeated swaps in later passes