Bubble Sort Algorithm

Bubble Sort is one of the simplest sorting algorithms. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until the list is sorted.

Despite its simplicity, Bubble Sort is not efficient for large datasets — it has a time complexity of O(n²).

Code Example

public class BubbleSortExample {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;

                    swapped = true;
                }
            }
            
            // If no two elements were swapped in the inner loop, the array is already sorted
            if (!swapped) break;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Original array:");
        printArray(arr);

        bubbleSort(arr);

        System.out.println("Sorted array:");
        printArray(arr);
    }

    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

Output

Original array:
64 34 25 12 22 11 90 
Sorted array:
11 12 22 25 34 64 90 

Code Explanation

• bubbleSort(int[] arr): Implements the sorting logic.
  • The outer loop runs n-1 times.
  • The inner loop compares adjacent elements and swaps them if they are in the wrong order.
  • The swapped flag is used to optimize performance — if no swaps occur during a full pass, the algorithm stops early.
• printArray(int[] arr): Utility method to display the contents of the array.
• Time Complexity:
  • Worst and Average Case: O(n²)
  • Best Case (already sorted): O(n), due to the swapped optimization.

Visual Explanation

Here’s a visual explanation of how Bubble Sort works, step-by-step, using the array:

[64, 34, 25, 12, 22, 11, 90]

🔁 Pass 1

Compare adjacent elements and swap if needed:

[64, 34, 25, 12, 22, 11, 90] → compare 64 & 34 → swap → [34, 64, 25, 12, 22, 11, 90]  
[34, 64, 25, 12, 22, 11, 90] → compare 64 & 25 → swap → [34, 25, 64, 12, 22, 11, 90]  
[34, 25, 64, 12, 22, 11, 90] → compare 64 & 12 → swap → [34, 25, 12, 64, 22, 11, 90]  
[34, 25, 12, 64, 22, 11, 90] → compare 64 & 22 → swap → [34, 25, 12, 22, 64, 11, 90]  
[34, 25, 12, 22, 64, 11, 90] → compare 64 & 11 → swap → [34, 25, 12, 22, 11, 64, 90]  
[34, 25, 12, 22, 11, 64, 90] → compare 64 & 90 → OK  

✅ Largest element (90) is now at the end

🔁 Pass 2

Now ignore the last element:

[34, 25, 12, 22, 11, 64, 90]
→ 34 > 25 → swap → [25, 34, 12, 22, 11, 64, 90]
→ 34 > 12 → swap → [25, 12, 34, 22, 11, 64, 90]
→ 34 > 22 → swap → [25, 12, 22, 34, 11, 64, 90]
→ 34 > 11 → swap → [25, 12, 22, 11, 34, 64, 90]
→ 34 < 64 → OK

✅ Second-largest element (64) is now in position

🔁 Further Passes

The process repeats:

• Pass 3: [25, 12, 22, 11, 34, 64, 90] → ends with 34 sorted
• Pass 4: [12, 22, 11, 25, 34, 64, 90] → ends with 25 sorted
• Pass 5: [12, 11, 22, 25, 34, 64, 90]
• Pass 6: [11, 12, 22, 25, 34, 64, 90]

🧩 Final Sorted Array

[11, 12, 22, 25, 34, 64, 90]