Bubble Sort

📖 Objective: Understand Bubble Sort, one of the simplest sorting algorithms, through illustrations and Java code.

📝 Table of Contents

1. What is Bubble Sort?
2. How Bubble Sort Works?
3. Java Implementation
4. Time and Space Complexity
5. Conclusion

🧠 What is Bubble Sort?

Bubble sort is one of the simplest sorting algorithms that sorts a list by repeatedly swapping adjacent elements that are in the wrong order. It is often used for educational purposes due to its simplicity, despite being inefficient for large datasets.

🛠 How Bubble Sort Works?

Consider the array: [5, 3, 8, 4, 6]

1. Compare the first two elements, 5 and 3. Swap them.
   • [3, 5, 8, 4, 6]
2. Compare the next two elements, 5 and 8. No swap needed.
   • [3, 5, 8, 4, 6]
3. Compare 8 and 4. Swap them.
   • [3, 5, 4, 8, 6]
4. Compare 8 and 6. Swap them.
   • [3, 5, 4, 6, 8]
5. The list is not sorted yet. Repeat steps 1-4.

After multiple iterations, you’ll end up with a sorted array.

📝 Implementation of Bubble Sort in Java

Below is the Java code for the Bubble Sort algorithm.

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 6};
        bubbleSort(arr);

        for(int i: arr) {
            System.out.print(i + " ");
        }
    }

    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]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }

            if (!swapped) break;
        }
    }
}

⏳ Time and Space Complexity

• Time Complexity: The worst-case and average-case time complexity is O(n²), but the best-case is O(n) when the array is already sorted.
• Space Complexity: The space complexity is O(1) as we are using constant extra space.

📚 Conclusion

You’ve now understood what Bubble Sort is, how it works, and how to implement it in Java. Despite its inefficiency for larger datasets, Bubble Sort provides an excellent introduction to sorting algorithms.

Thank you for reading! If you find this tutorial helpful, please share it with your friends.