Bubble Sort is an elementary sorting algorithm that operates by repeatedly scanning an unsorted list, comparing each pair of adjacent elements, and swapping them if they are in the wrong order. This process continues until the entire list is sorted, with larger elements gradually "bubbling up" to the end of the list over each iteration.

Basic Implementation of Bubble Sort

The following code demonstrates the core implementation of bubble sort in C, along with a helper function to print array elements:

#include <stdio.h>

// Sorts an array using bubble sort algorithm
void bubble_sort(int nums[], int length) {
    int outer_idx, inner_idx, swap_val;
    for (outer_idx = 0; outer_idx < length - 1; outer_idx++) {
        for (inner_idx = 0; inner_idx < length - outer_idx - 1; inner_idx++) {
            if (nums[inner_idx] > nums[inner_idx + 1]) {
                // Swap adjacent elements
                swap_val = nums[inner_idx];
                nums[inner_idx] = nums[inner_idx + 1];
                nums[inner_idx + 1] = swap_val;
            }
        }
    }
}

// Prints elements of an array
void print_array(int nums[], int length) {
    int idx;
    for (idx = 0; idx < length; idx++) {
        printf("%d ", nums[idx]);
    }
    printf("\n");
}

int main() {
    int sample_arr[] = {64, 34, 25, 12, 22, 11, 90};
    int arr_length = sizeof(sample_arr) / sizeof(sample_arr[0]);
    
    printf("Unsorted array:\n");
    print_array(sample_arr, arr_length);
    
    bubble_sort(sample_arr, arr_length);
    
    printf("Sorted array:\n");
    print_array(sample_arr, arr_length);
    
    return 0;
}

Code Explanation

• bubble_sort Function: Uses two nested loops to process the array. The outer loop controls the number of passes, while the inner loop iterates through the unsorted segment, comparing and swapping adjacent elements as needed.
• print_array Function: Iterates over the array and prints each elemant, enabling easy verification of the sorted result.
• main Function: Initializes a sample array, calculates its length, prints the unsorted state, applies the bubble sort algorithm, and prints the final sorted array.

Optimizations for Bubble Sort

While bubble sort is straightforward, its default performance is suboptimal for larger datasets. Below are two common optimiaztions to improve its efficiency:

1. Early Termination with a Swap Flag

Adding a flag to track swap activity allows the algorithm to terminate early if the array becomes sorted before all passes are completed, eliminating unnecessary computations.

void optimized_bubble_sort(int nums[], int length) {
    int outer_idx, inner_idx, swap_val;
    int has_swapped;
    for (outer_idx = 0; outer_idx < length - 1; outer_idx++) {
        has_swapped = 0;
        for (inner_idx = 0; inner_idx < length - outer_idx - 1; inner_idx++) {
            if (nums[inner_idx] > nums[inner_idx + 1]) {
                swap_val = nums[inner_idx];
                nums[inner_idx] = nums[inner_idx + 1];
                nums[inner_idx + 1] = swap_val;
                has_swapped = 1;
            }
        }
        // Exit early if no swaps occurred in this pass
        if (!has_swapped) {
            break;
        }
    }
}

2. Bidirectional Bubble Sort (Cocktail Sort)

This variation traverses the array in both left-to-right and right-to-left directions during each pass, which efficiently moves smaller elements to the start of the list, reducing iteration count for partially sorted arrays.

void cocktail_sort(int nums[], int length) {
    int has_swapped = 1;
    int start = 0;
    int end = length - 1;
    int idx, swap_val;

    while (has_swapped) {
        has_swapped = 0;
        // Traverse left to right
        for (idx = start; idx < end; idx++) {
            if (nums[idx] > nums[idx + 1]) {
                swap_val = nums[idx];
                nums[idx] = nums[idx + 1];
                nums[idx + 1] = swap_val;
                has_swapped = 1;
            }
        }
        if (!has_swapped) {
            break;
        }
        has_swapped = 0;
        end--;
        // Traverse right to left
        for (idx = end - 1; idx >= start; idx--) {
            if (nums[idx] > nums[idx + 1]) {
                swap_val = nums[idx];
                nums[idx] = nums[idx + 1];
                nums[idx + 1] = swap_val;
                has_swapped = 1;
            }
        }
        start++;
    }
}

Performance Analysis

• Time Complexity:
  • Worst-case and average-case: O(n²) due to nested iterations over the array.
  • Best-case: O(n) when using the early termination flag, as the algorithm exits immediately if the array is already sorted.
• Space Complexity: O(1), as it only uses a constant amount of additional memory for temporary variables and flags.
• Stability: Bubble sort is a stable algorithm, meaning it preserves the relative order of elements with equal values.

Practical Use Cases

Despite its O(n²) average time complexity, bubble sort remains useful in specific scenarios:

• Educational Purposes: Its simple logic makes it an ideal starting point for teaching basic sorting concepts to new programmers.
• Small Datasets: For very small arrays, the overhead of more complex algorithms may outweigh their performance banefits.
• Stable Sorting Requirements: In cases where maintaining the relative order of equal elements is critical, bubble sort’s stability is a valuable feature.