Bubble Sort Algorithm in DSA Java

Mental Model

Bubble sort repeatedly swaps adjacent items if they are in the wrong order, pushing the largest unsorted item to the end each pass.

Analogy: Imagine bubbles rising in water: the biggest bubble slowly moves up to the surface by swapping places with smaller bubbles below it.

5 3 8 4 2
↑
Start with unsorted list, pointer at first element

Dry Run Walkthrough

Input: list: 5 -> 3 -> 8 -> 4 -> 2, sort ascending

Goal: Sort the list so numbers go from smallest to largest

Step 1: Compare 5 and 3, swap because 5 > 3

3 -> 5 -> 8 -> 4 -> 2

Why: Smaller number moves left, bigger moves right

Step 2: Compare 5 and 8, no swap because 5 < 8

3 -> 5 -> 8 -> 4 -> 2

Why: Order is correct, no change

Step 3: Compare 8 and 4, swap because 8 > 4

3 -> 5 -> 4 -> 8 -> 2

Why: Push bigger number right

Step 4: Compare 8 and 2, swap because 8 > 2

3 -> 5 -> 4 -> 2 -> 8

Why: Largest number bubbles to the end

Step 5: Start next pass, compare 3 and 5, no swap

3 -> 5 -> 4 -> 2 -> 8

Why: First two are in order

Step 6: Compare 5 and 4, swap because 5 > 4

3 -> 4 -> 5 -> 2 -> 8

Why: Smaller number moves left

Step 7: Compare 5 and 2, swap because 5 > 2

3 -> 4 -> 2 -> 5 -> 8

Why: Push bigger number right

Step 8: Start next pass, compare 3 and 4, no swap

3 -> 4 -> 2 -> 5 -> 8

Why: Order is correct

Step 9: Compare 4 and 2, swap because 4 > 2

3 -> 2 -> 4 -> 5 -> 8

Why: Smaller number moves left

Step 10: Start next pass, compare 3 and 2, swap because 3 > 2

2 -> 3 -> 4 -> 5 -> 8

Why: Final swap to order smallest numbers

Result:

2 -> 3 -> 4 -> 5 -> 8

Annotated Code

DSA Java

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) {
                break;
            }
        }
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(" -> ");
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        System.out.print("Original list: ");
        printArray(arr);
        bubbleSort(arr);
        System.out.print("Sorted list: ");
        printArray(arr);
    }
}

for (int i = 0; i < n - 1; i++) {

repeat passes to bubble largest unsorted element to the end

boolean swapped = false;

track if any swaps happen this pass to stop early if sorted

for (int j = 0; j < n - 1 - i; j++) {

compare adjacent pairs up to last unsorted element

if (arr[j] > arr[j + 1]) {

check if current pair is out of order

swap arr[j] and arr[j + 1]

exchange elements to move bigger one right

swapped = true;

mark that a swap happened this pass

if (!swapped) { break; }

stop early if no swaps, list is sorted

Output

Original list: 5 -> 3 -> 8 -> 4 -> 2

Sorted list: 2 -> 3 -> 4 -> 5 -> 8

Complexity Analysis

Time: O(n^2) because each element is compared with others in nested loops

Space: O(1) because sorting is done in place without extra storage

vs Alternative: Compared to more advanced sorts like quicksort (O(n log n)), bubble sort is slower but simpler to understand and implement

Edge Cases

empty array

function returns immediately without error

DSA Java

for (int i = 0; i < n - 1; i++) {

array with one element

no swaps needed, returns immediately

DSA Java

for (int i = 0; i < n - 1; i++) {

already sorted array

early break after first pass because no swaps

DSA Java

if (!swapped) { break; }

When to Use This Pattern

When you see a problem asking to sort a small list with simple swaps, bubble sort is a good first approach because it repeatedly swaps neighbors to order the list.

Common Mistakes

Mistake: Not reducing the inner loop range each pass, causing unnecessary comparisons
Fix: Decrease inner loop limit by i each pass to avoid checking sorted tail

Mistake: Not using a swapped flag to stop early, causing extra passes
Fix: Add a swapped boolean to break early if no swaps happen

Summary

Bubble sort repeatedly swaps adjacent elements to sort a list.

Use it for small or nearly sorted lists where simplicity matters more than speed.

The key insight is that the largest unsorted element 'bubbles' to the end each pass.

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