Bubble Sort Algorithm in DSA Java - Execution Trace

Concept Flow - Bubble Sort Algorithm

Start with array

↓

Compare adjacent elements

↓

If left > right?

↓

Swap elements

↓

Reached end of array?

↓

Repeat pass

↓

Done

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

Execution Sample

DSA Java

int[] arr = {5, 3, 8, 1, 2};
for (int i = 0; i < arr.length - 1; i++) {
  for (int j = 0; j < arr.length - 1 - i; j++) {
    if (arr[j] > arr[j + 1]) {
      int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp;
    }
  }
}

Sorts the array by repeatedly swapping adjacent elements if they are in wrong order.

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 more passes needed	Array sorted	No	[1, 2, 3, 5, 8]

💡 After 4 passes, no swaps needed; 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]
i	0	0	0	1	2	3	4 (loop ends)
j	0	1	3	2	2	1	-

Key Moments - 3 Insights

Why do we reduce the inner loop's 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.

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

Swapping only when left > right ensures smaller elements bubble to the front. This is shown in execution_table rows like 1.1 and 1.3 where swaps happen only if condition is true.

When does the algorithm stop?

It stops when a full pass completes with no swaps, meaning the array is sorted. This is shown in the exit row where no swaps occur and the array is fully sorted.

Visual Quiz - 3 Questions

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

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

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

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

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

💡 Hint

Check the 'Array State' column in execution_table row 2.2.

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 State' column and the exit note in execution_table.

If we remove the swap condition, what happens to the array after step 1.1?

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

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

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

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

💡 Hint

Without swap condition, no swaps occur; array remains unchanged after step 1.1.

Concept Snapshot

Bubble Sort Algorithm:
- Repeatedly compare adjacent elements
- Swap if left > right
- Largest elements 'bubble' to the end each pass
- Reduce inner loop range each pass
- Stop when no swaps in a full pass
- Time: O(n²), simple but inefficient for large arrays

Full Transcript

Bubble Sort works by comparing pairs of adjacent elements in an array. If the left element is bigger, they swap places. This process repeats for the whole array, pushing the largest unsorted element to the end. Each pass reduces the number of elements to check because the end elements become sorted. The algorithm stops when a full pass happens with no swaps, meaning the array is sorted. The execution table shows each comparison and swap step, and the variable tracker shows how the array changes after each swap. Key moments clarify why the inner loop shrinks and when the algorithm stops. The visual quiz tests understanding of array states at different steps.

Practice

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

easy

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

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

C. Use a pivot to partition the list into smaller parts

D. Divide the list into halves and sort each half separately

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

3. Final Answer:

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

4. Quick Check:

   Bubble Sort = Swap adjacent pairs [OK]

Hint: Bubble sort swaps neighbors repeatedly until sorted [OK]

Common Mistakes:

• Confusing bubble sort with quicksort or merge sort
• Thinking bubble sort divides the list
• Assuming bubble sort inserts elements directly

2. Which of the following is the correct syntax to swap two elements arr[i] and arr[i+1] in Java during bubble sort?

easy

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

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

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

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

Solution

1. Step 1: Understand swapping in Java arrays

   To swap, use a temporary variable to hold one value, then assign values accordingly.

2. Step 2: Check each option

   int temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; correctly uses a temp variable. arr[i] = arr[i+1]; arr[i+1] = arr[i]; overwrites arr[i] before saving it. swap(arr[i], arr[i+1]); is invalid syntax in Java. int temp = arr[i+1]; arr[i] = arr[i+1]; arr[i+1] = temp; overwrites arr[i] without saving original arr[i].

3. Final Answer:

   int temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; -> Option A

4. Quick Check:

   Use temp variable to swap [OK]

Hint: Always use a temp variable to swap two array elements [OK]

Common Mistakes:

• Overwriting one element before saving it
• Using a swap function that doesn't exist in Java
• Swapping without a temporary variable

3. What will be the output array after one full pass of bubble sort on int[] arr = {5, 3, 8, 4, 2}?

medium

A. [3, 5, 8, 4, 2]

B. [2, 3, 4, 5, 8]

C. [5, 3, 4, 2, 8]

D. [3, 5, 4, 2, 8]

Solution

1. Step 1: Perform one pass of bubble sort

   Compare and swap adjacent elements if needed:
   5 and 3: swap -> [3,5,8,4,2]
   5 and 8: no swap
   8 and 4: swap -> [3,5,4,8,2]
   8 and 2: swap -> [3,5,4,2,8]

2. Step 2: Result after first pass

   The largest element 8 moves to the end. The array is [3,5,4,2,8].

3. Final Answer:

   [3, 5, 4, 2, 8] -> Option D

4. Quick Check:

   One pass moves largest to end [OK]

Hint: One pass pushes largest element to the end [OK]

Common Mistakes:

• Not swapping all needed pairs in one pass
• Assuming full sort after one pass
• Confusing order of swaps

4. Identify the error in the following bubble sort code snippet:

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

medium

A. Inner loop should run till arr.length - i - 1 to avoid index out of bounds

B. Outer loop should start from 1 instead of 0

C. Swap logic is incorrect, should swap arr[j+1] with arr[j-1]

D. No error, code is correct

Solution

1. Step 1: Analyze inner loop range

   Inner loop runs till arr.length, but accesses arr[j+1]. When j = arr.length - 1, arr[j+1] causes index out of bounds.

2. Step 2: Correct inner loop limit

   Inner loop should run till arr.length - i - 1 to avoid out of bounds and optimize sorting.

3. Final Answer:

   Inner loop should run till arr.length - i - 1 to avoid index out of bounds -> Option A

4. Quick Check:

   Prevent arr[j+1] out of bounds by limiting inner loop [OK]

Hint: Inner loop limit must prevent arr[j+1] overflow [OK]

Common Mistakes:

• Ignoring array index limits in inner loop
• Incorrect swap indices
• Assuming code runs without error

5. Given an array int[] arr = {4, 2, 7, 1, 3}, how many total swaps will bubble sort perform to fully sort the array?

hard

A. 7

B. 5

C. 6

D. 8

Solution

1. Step 1: Count swaps in each pass

   Pass 1:
   4>2 swap (1)
   4>7 no swap
   7>1 swap (2)
   7>3 swap (3)
   Array: [2,4,1,3,7]
   Pass 2:
   4>1 swap (4)
   4>3 swap (5)
   Array: [2,1,3,4,7]
   Pass 3:
   2>1 swap (6)
   Array: [1,2,3,4,7]
   Pass 4:
   No swaps

2. Step 2: Total swaps

   Total swaps = 6 swaps counted in passes 1-3.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Count swaps carefully per pass [OK]

Hint: Count swaps each pass until no swaps occur [OK]

Common Mistakes:

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