🔁 Understanding Bubble Sort in DSA: Algorithm, Example, and Code Implementation

Sorting is one of the most fundamental operations in programming. It helps organize data in a specific order (ascending or descending) for easier searching and processing.

Among many sorting algorithms, Bubble Sort is one of the simplest and most beginner-friendly algorithms used to understand the concept of sorting.

💡 What Is Bubble Sort?

Bubble Sort is a simple comparison-based sorting algorithm. It works by repeatedly swapping adjacent elements if they are in the wrong order.

This process continues until the entire array is sorted. The largest (or smallest) element "bubbles up" to its correct position after each iteration — hence the name Bubble Sort.

⚙️ Working of Bubble Sort

Let’s understand how Bubble Sort works step-by-step with an example.

Example
Consider the array → [5, 2, 8, 4, 1]

🔹 Step-by-Step Process:

Compare the first two elements (5 and 2). Since 5 > 2, swap them → [2, 5, 8, 4, 1]
Compare 5 and 8 → No swap (as 5 < 8).
Compare 8 and 4 → Swap → [2, 5, 4, 8, 1]
Compare 8 and 1 → Swap → [2, 5, 4, 1, 8]

Now the largest element (8) is at the correct position.

The process repeats for the remaining elements until the array becomes completely sorted:
[1, 2, 4, 5, 8]

🧠 Algorithm of Bubble Sort

Step 1: Start from the first element of the array.
Step 2: Compare the current element with the next one.
Step 3: If the current element is greater than the next, swap them.
Step 4: Move to the next element and repeat until the end of the array.
Step 5: Repeat steps 1–4 until no swaps are needed (array is sorted).

💻 C Program for Bubble Sort

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) {
        // Flag to optimize if the array is already sorted
        int swapped = 0;
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap elements
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        // If no two elements were swapped, array is sorted
        if (swapped == 0)
            break;
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {5, 2, 8, 4, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    bubbleSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

🧩 Output

Original array: 5 2 8 4 1  
Sorted array: 1 2 4 5 8

🕒 Time and Space Complexity

Case	Time Complexity	Explanation
Best Case	O(n)	Array already sorted (optimized version)
Average Case	O(n²)	Comparisons and swaps for partially sorted data
Worst Case	O(n²)	Reverse order data
Space Complexity	O(1)	In-place sorting

⚡ Advantages of Bubble Sort

✅ Easy to understand and implement.
✅ Works well for small datasets.
✅ No extra space required (in-place algorithm).

⚠️ Disadvantages of Bubble Sort

❌ Inefficient for large datasets (O(n²) time complexity).
❌ Performs unnecessary comparisons even when the array is almost sorted.

🚀 When to Use Bubble Sort

Use Bubble Sort only for:

Small arrays where simplicity matters.
Educational or learning purposes to understand sorting logic.

For large datasets, prefer advanced algorithms like Merge Sort, Quick Sort, or Heap Sort.

🏁 Conclusion

Bubble Sort is the perfect starting point for understanding sorting algorithms in DSA. While it’s not efficient for big data, it helps you grasp core concepts like comparison, swapping, and iteration — essential building blocks for advanced algorithms.