Bubble Sort

Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly compares adjacent elements in an array and swaps them if they are in the wrong order. This process continues until the array is completely sorted.

The name "bubble sort" comes from the way larger elements “bubble up” to the end of the array in each iteration.

How Does Bubble Sort Work?

The algorithm follows these basic steps:

Start at the beginning of the array.
Compare the first two elements.
If the first is greater than the second, swap them.
Move to the next pair and repeat the comparison and swap if needed.
Continue this process for each pair until the end of the array.
Repeat the whole process for the remaining unsorted portion.

Example: Bubble Sort

Let’s sort the array {5, 1, 4, 2, 8}

Pass 1

Compare 5 and 1 → swap → {1, 5, 4, 2, 8}

Compare 5 and 4 → swap → {1, 4, 5, 2, 8}

Compare 5 and 2 → swap → {1, 4, 2, 5, 8}

Compare 5 and 8 → no swap → {1, 4, 2, 5, 8}

Pass 2

Compare 1 and 4 → no swap

Compare 4 and 2 → swap → {1, 2, 4, 5, 8}

Compare 4 and 5 → no swap

Compare 5 and 8 → no swap

Pass 3

Compare 1 and 2 → no swap

Compare 2 and 4 → no swap

Compare 4 and 5 → no swap → sorted

Array is now sorted: {1, 2, 4, 5, 8}

When to Use Bubble Sort?

When simplicity is more important than efficiency
For teaching and learning purposes
When working with very small or nearly sorted arrays
To introduce the idea of sorting and swapping elements

Time and Space Complexity

Case	Time Complexity	Explanation
Best Case	O(n)	If array is already sorted (with optimisation)
Average Case	O(n²)	Nested loops for each element
Worst Case	O(n²)	Array sorted in reverse order
Space	O(1)	In-place sorting, no extra memory used

Advantages of Bubble Sort

Simple to understand and implement
No extra space required (In-place algorithm)
Can be optimized to detect already sorted array
Useful for small datasets or educational purposes

Disadvantages of Bubble Sort

Inefficient on large datasets
High time complexity compared to better algorithms (Merge, Quick, Heap)
Not suitable for performance-critical applications

Algorithm for Bubble Sort

Step 1: Start
Step 2: Repeat for i = 0 to n - 2
Step 3: Repeat for j = 0 to n - i - 2
Step 4: If arr[j] > arr[j + 1] then
          Swap arr[j] and arr[j + 1]
Step 5: End inner loop
Step 6: End outer loop
Step 7: Stop

n is the number of elements in the array.
The outer loop ensures the process is repeated n-1 times.
The inner loop compares and swaps adjacent elements.
After each pass, the largest unsorted element moves to its correct position at the end.

C Program for Bubble Sort

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0; // Optimization to check if array is already sorted
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        if (swapped == 0)
            break; // Stop if array is already sorted
    }
}

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

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

    printf("Original Array:\n");
    printArray(arr, n);

    bubbleSort(arr, n);

    printf("Sorted Array:\n");
    printArray(arr, n);

    return 0;
}

Numerical Questions for Bubble Sort

Sort {64, 34, 25, 12, 22, 11, 90} using Bubble Sort.
Apply Bubble Sort on {9, 7, 5, 3, 1} and count the number of swaps.
Sort the following array using Bubble Sort and show all the passes {5, 2, 9, 1, 5, 6}
Apply Bubble Sort on the array {99, 88, 77, 66, 55} . Show How many total comparisons and swaps are needed?
Sort the numbers using Bubble Sort {64, 25, 12, 22, 11} Count the total number of swaps performed.

Menu