Bubble Sort operates by repeatedly comparing adjacent elements in an array and swapping them if they are in the wrong order. This process is repeated until the entire array is sorted, with larger elements gradually moving towards the end like bubbles rising to the surface.

Bubble Sort is suitable for small datasets or partially sorted data and is often used for educational purposes to illustrate basic sorting concepts.

Algorithm Steps

1. Compare each pair of adjacent elements in the array.
2. If the first element is greater than the second, swap them.
3. Repeat this process for every adjacent pair from the start to the end of the array. After each full pass, the largest unosrted element moves to its correct position at the end.
4. Continue rpeeating the process for the remaining unsorted portion of the array, excluding the last sorted element each time.
5. Stop when no swaps are needed in a complete pass.

Code Implementation

#include <stdio.h>

void bubbleSort(int array[], int size) {
    int outer, inner, swapTemp;
    for (outer = 0; outer < size - 1; outer++) {
        for (inner = 0; inner < size - 1 - outer; inner++) {
            if (array[inner] > array[inner + 1]) {
                swapTemp = array[inner];
                array[inner] = array[inner + 1];
                array[inner + 1] = swapTemp;
            }
        }
    }
}

int main() {
    int values[] = {45, 12, 67, 23, 89, 33, 71, 54, 18, 92};
    int count = sizeof(values) / sizeof(values[0]);
    bubbleSort(values, count);
    for (int idx = 0; idx < count; idx++) {
        printf("%d ", values[idx]);
    }
    return 0;
}

Function Variations

Ascending Order

void bubbleSortAsc(unsigned short *items, unsigned char total) {
    unsigned char pass, pos;
    unsigned short holder;
    for (pass = 0; pass < total - 1; pass++) {
        for (pos = 0; pos < total - 1 - pass; pos++) {
            if (items[pos] > items[pos + 1]) {
                holder = items[pos];
                items[pos] = items[pos + 1];
                items[pos + 1] = holder;
            }
        }
    }
}

Descending Order

void bubbleSortDesc(unsigned short *items, unsigned char total) {
    unsigned char pass, pos;
    unsigned short holder;
    for (pass = 0; pass < total - 1; pass++) {
        for (pos = 0; pos < total - 1 - pass; pos++) {
            if (items[pos] < items[pos + 1]) {
                holder = items[pos];
                items[pos] = items[pos + 1];
                items[pos + 1] = holder;
            }
        }
    }
}

Loop Explanation

Outer Loop

• Iterates pass from 0 to total - 2.
• Each iteration reduces the unsorted portion by one element after the inner loop completes.
• After total - 1 passes, the smallest element naturally falls into place.

Inner Loop

• Compares adjacent elements from index 0 to total - 2 - pass.
• Reduces comparisons each pass as the largest elements are already sorted at the end.
• Swaps elements when they are out of order.

Optimized Version with Early Termination

An optimized version uses a flag to detect if any swaps occurred during a pass. If no swaps happen, the array is already sorted, and the algorithm can terminate early.

void optimizedBubbleSort(unsigned short *items, unsigned char total) {
    unsigned char pass, pos, swapped;
    unsigned short holder;
    for (pass = 0; pass < total - 1; pass++) {
        swapped = 0;
        for (pos = 0; pos < total - 1 - pass; pos++) {
            if (items[pos] > items[pos + 1]) {
                holder = items[pos];
                items[pos] = items[pos + 1];
                items[pos + 1] = holder;
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
}

Time Complexity Analysis

• Best Case: O(n) when the array is already sorted, requiring only one pass.
• Worst Case: O(n²) when the array is reverse sorted, requiring maximum comparisons and swaps.
• Average Case: O(n²) for random data.

Performance Characteristics

Advantages

• Simple to understand and implement.
• Stable sorting algorithm (preserves order of equal elements).
• Space-efficient with O(1) auxiliary space.

Disadvantages

• Inefficient for large datasets due to quadratic time complexity.
• Multiple passes required even for nearly sorted arrays.
• Not suitable for performance-critical applications.