Bubble Sort in C: A Step-by-Step Guide

Welcome to C-Language Series #129! In this installment, we'll dive into one of the simplest yet fundamental sorting algorithms: Bubble Sort. While often overlooked for its efficiency in real-world large-scale applications, understanding Bubble Sort is crucial for grasping basic sorting concepts and building a strong foundation in algorithm design.

What is Bubble Sort?

Bubble Sort is a straightforward sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Imagine bubbles rising to the surface – larger elements "bubble up" to their correct position at one end of the array, or smaller elements "sink" to the other end, with each pass. This analogy gives the algorithm its distinctive name.

How Bubble Sort Works (The Mechanism)

Let's break down the process with a simple array example: [5, 1, 4, 2, 8]. We'll sort this array in ascending order.

• Initial Array: [5, 1, 4, 2, 8] (n=5 elements)
• Pass 1:
  • Compare 5 and 1. Since 5 > 1, swap them. Array: [1, 5, 4, 2, 8]
  • Compare 5 and 4. Since 5 > 4, swap them. Array: [1, 4, 5, 2, 8]
  • Compare 5 and 2. Since 5 > 2, swap them. Array: [1, 4, 2, 5, 8]
  • Compare 5 and 8. No swap needed. Array: [1, 4, 2, 5, 8]
  At the end of Pass 1, the largest element (8) has "bubbled" to its correct position at the end of the array. The unsorted part is now [1, 4, 2, 5].
• Pass 2: (We now only need to consider the first n-1 elements, as 8 is sorted)
  • Compare 1 and 4. No swap. Array: [1, 4, 2, 5, 8]
  • Compare 4 and 2. Since 4 > 2, swap them. Array: [1, 2, 4, 5, 8]
  • Compare 4 and 5. No swap. Array: [1, 2, 4, 5, 8]
  At the end of Pass 2, the second largest element (5) is now in its correct position. The unsorted part is [1, 2, 4].
• Pass 3: (Consider the first n-2 elements)
  • Compare 1 and 2. No swap. Array: [1, 2, 4, 5, 8]
  • Compare 2 and 4. No swap. Array: [1, 2, 4, 5, 8]
  At the end of Pass 3, the third largest element (4) is sorted. The unsorted part is [1, 2].
• Pass 4: (Consider the first n-3 elements)
  • Compare 1 and 2. No swap. Array: [1, 2, 4, 5, 8]
  After Pass 4, the array is fully sorted.

Bubble Sort Algorithm (Pseudocode)

The core logic can be summarized with this pseudocode:

function bubbleSort(array A, size n):
    // Outer loop for passes
    for i from 0 to n-2:
        // Inner loop for comparisons and swaps in current pass
        // Last 'i' elements are already in place, so we iterate less each time
        for j from 0 to n-2-i:
            if A[j] > A[j+1]:
                // Swap if the element on the left is greater than the one on the right
                swap A[j] and A[j+1]
    

C Implementation of Bubble Sort

Let's translate this into a C function. We'll include a helper function to swap two integers and another to print the array for clear demonstration.

#include <stdio.h> // Required for printf

// Function to swap two integer elements
void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

// Function to perform Bubble Sort on an integer array
void bubbleSort(int arr[], int n) {
    int i, j;
    // Outer loop: iterate through each pass
    for (i = 0; i < n - 1; i++) {
        // Inner loop: compare adjacent elements and swap them
        // The '-i-1' ensures we don't re-compare elements that are already sorted
        for (j = 0; j < n - i - 1; j++) {
            // If the current element is greater than the next
            if (arr[j] > arr[j+1]) {
                swap(&arr[j], &arr[j+1]); // Swap them
            }
        }
    }
}

// Function to print an array's elements
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Driver program to test the Bubble Sort function
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90}; // Sample array
    int n = sizeof(arr) / sizeof(arr[0]); // Calculate number of elements

    printf("Original array: \n");
    printArray(arr, n); // Print the unsorted array

    bubbleSort(arr, n); // Sort the array

    printf("Sorted array: \n");
    printArray(arr, n); // Print the sorted array

    return 0; // Indicate successful execution
}
    

Explanation of the C Code:

• The swap function takes two integer pointers and exchanges their values. This is a common utility for sorting.
• The outer loop (for (i = 0; i < n - 1; i++)) runs n-1 times. Each iteration completes one "pass" of the bubble sort, moving the next largest element to its correct position.
• The inner loop (for (j = 0; j < n - i - 1; j++)) traverses the unsorted portion of the array. The -i-1 part is crucial: after each pass i, the largest i elements are already at the end of the array in their final sorted positions, so we don't need to compare them again.
• Inside the inner loop, if (arr[j] > arr[j+1]) compares adjacent elements. If they are in the wrong order (i.e., the left is larger than the right for ascending sort), they are swapped.

Optimized Bubble Sort

A practical optimization can be added to Bubble Sort: if a pass completes without any swaps, it means the array is already sorted, and we can terminate the algorithm early. This significantly improves performance in the best-case scenario (an already sorted array).

#include <stdio.h>
#include <stdbool.h> // Required for using the 'bool' type

// Function to swap two integer elements
void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

// Optimized Bubble Sort function
void optimizedBubbleSort(int arr[], int n) {
    int i, j;
    bool swapped; // Flag to check if any swap happened in a pass

    for (i = 0; i < n - 1; i++) {
        swapped = false; // Reset flag at the beginning of each pass
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(&arr[j], &arr[j+1]);
                swapped = true; // Mark that a swap occurred
            }
        }
        // If no two elements were swapped by the inner loop,
        // then the array is sorted, and we can break early.
        if (swapped == false)
            break;
    }
}

// Function to print an array's elements
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Driver program to test the optimized Bubble Sort
int main() {
    int arr1[] = {10, 20, 30, 40, 50}; // An already sorted array
    int n1 = sizeof(arr1) / sizeof(arr1[0]);

    printf("Original array 1 (already sorted): \n");
    printArray(arr1, n1);

    optimizedBubbleSort(arr1, n1); // This will sort very quickly
    printf("Sorted array 1: \n");
    printArray(arr1, n1);

    printf("\n-----------------------------------\n");

    int arr2[] = {5, 1, 4, 2, 8}; // A partially unsorted array
    int n2 = sizeof(arr2) / sizeof(arr2[0]);

    printf("Original array 2: \n");
    printArray(arr2, n2);

    optimizedBubbleSort(arr2, n2);
    printf("Sorted array 2: \n");
    printArray(arr2, n2);

    return 0;
}
    

In the optimized version, the swapped boolean flag is introduced. If, after an entire pass through the inner loop, no swaps occur (i.e., swapped remains false), it means all elements are already in their correct order. The outer loop then terminates prematurely, avoiding unnecessary comparisons and passes.

Time and Space Complexity

Understanding the efficiency of an algorithm is crucial for choosing the right one for a given task.

• Time Complexity:
  • Worst Case: O(n^2) (Big O of n-squared). This occurs when the array is sorted in reverse order (e.g., [8, 5, 4, 2, 1]), requiring the maximum number of comparisons and swaps.
  • Average Case: O(n^2). For a randomly ordered array, the number of comparisons and swaps generally remains proportional to the square of the number of elements.
  • Best Case: O(n) (Big O of n). This happens when the array is already sorted. With the optimization, only one pass is needed to confirm the array is sorted, making n-1 comparisons. Without optimization, it would still be O(n^2).
• Space Complexity: O(1) (Big O of 1). Bubble Sort is an in-place sorting algorithm, meaning it only requires a constant amount of extra memory for temporary variables (like temp in the swap function), regardless of the input size.

Advantages and Disadvantages of Bubble Sort

Advantages:

• Simplicity: It's one of the easiest sorting algorithms to understand and implement, making it great for beginners.
• Space Efficiency: It's an in-place algorithm, requiring only O(1) auxiliary space.
• Stability: It's a stable sorting algorithm, meaning that elements with equal values maintain their relative order in the sorted output.

Disadvantages:

• Inefficiency: Its O(n^2) average and worst-case time complexity makes it highly inefficient for large datasets.
• Performance: Compared to more advanced algorithms like Quick Sort or Merge Sort (which have O(n log n) complexity), Bubble Sort is significantly slower for larger inputs.

When to Use Bubble Sort?

Given its performance characteristics, Bubble Sort is rarely used in practical applications for large datasets. Its primary uses include:

• Educational Purposes: It's an excellent introductory algorithm for teaching basic sorting concepts, loop structures, and conditional logic.
• Very Small Datasets: For extremely small arrays (e.g., less than 10-20 elements), the overhead of more complex algorithms might not be justified, and Bubble Sort could be sufficient.
• When data is almost sorted: The optimized version performs relatively well (O(n) in the best case) if the array is already sorted or nearly sorted, as it quickly detects and skips unnecessary passes.

Conclusion

Bubble Sort, despite its quadratic time complexity, serves as a fundamental stepping stone in understanding how sorting algorithms work. Its intuitive nature makes it perfect for beginners to grasp concepts like comparisons, swaps, and algorithm efficiency. While you likely won't use it for production-level sorting of massive datasets, its principles underpin more advanced techniques. Mastering Bubble Sort lays the groundwork for tackling more sophisticated algorithms.

Stay tuned for the next installment in our C-Language Series, where we'll explore more efficient sorting algorithms!