Optimizing Bubble Sort

While our current C implementation of Bubble Sort works perfectly, it has one major drawback: it's not very smart. It will run through all n-1 passes even if the array becomes sorted in the very first pass. Imagine giving it an array that is already sorted, like [1, 2, 3, 4, 5]. Our current code will still loop through it again and again, making comparisons even when no swaps are happening. This is a significant waste of processing power. In this section, we'll explore a simple yet highly effective way to optimize Bubble Sort, making it "smart" enough to stop early as soon as it realizes the array is fully sorted.

5.1: Early Termination Optimization

The most popular optimization for Bubble Sort is known as Early Termination. The logic is simple: if we go through an entire pass (a full run of the inner loop) and we don't need to make a single swap, what does that tell us? It means every element is already in its correct, sorted position.

So, why continue looping?

We can modify our function to keep track of whether any swaps were made during a pass. If a pass completes without any swaps, a "flag" variable tells our outer loop to break early, saving us from countless redundant comparisons.

Let's look at the optimized Bubble Sort C code:

#include <stdio.h> #include <stdbool.h> // Include this header to use 'bool' type // A helper function to swap two integer values void swap(int *a, int *b) {    int temp = *a;    *a = *b;    *b = temp; } // The OPTIMIZED Bubble Sort function void optimizedBubbleSort(int arr[], int n) {    int i, j;    bool swapped; // Our "flag" variable        // Outer loop: Controls the number of passes    for (i = 0; i < n - 1; i++) {                // 1. Set the flag to false at the start of each pass        swapped = false;                // Inner loop: Performs the comparisons        for (j = 0; j < n - i - 1; j++) {                        if (arr[j] > arr[j + 1]) {                swap(&arr[j], &arr[j + 1]);                                // 2. If we swap, set the flag to true                swapped = true;            }        }                // 3. After the inner loop, check the flag        // If no swaps were made (swapped is still false),        // the array is sorted.        if (swapped == false) {            break; // Exit the outer loop early        }    } } // A utility function to print the array void printArray(int arr[], int size) {    for (int i = 0; i < size; i++) {        printf("%d ", arr[i]);    }    printf("\n"); } // Main function to drive the program int main() {    // Example 1: Nearly sorted array    int arr[] = {1, 2, 4, 3, 5, 6};    int n = sizeof(arr) / sizeof(arr[0]);        printf("Nearly sorted array (Unsorted): \n");    printArray(arr, n);        optimizedBubbleSort(arr, n);        printf("Sorted array: \n");    printArray(arr, n);        return 0; }

In this example, the un-optimized version would have run n-1 = 5 passes. Our optimized Bubble Sort will sort the array in just 2 passes and then terminate, making it much more efficient.

5.1.1: Reducing Comparisons When the Array is Sorted

The "magic" of this optimization comes down to reducing comparisons when the array is sorted, using the swapped flag. Let's trace the logic:

Set a Check

Before we start a new pass (the outer loop), we assume the best: we set swapped = false. We presume the array is sorted until proven otherwise.

Perform Comparisons

We run the inner loop as usual, comparing adjacent elements.

Flag the Swap

If we find two elements that are out of order (e.g., arr[j] > arr[j+1]) and we perform a swap(), we immediately raise the flag by setting swapped = true. This tells the outer loop, "Work is not done yet. We had to make a change in this pass."

Check the Flag

After the inner loop finishes its run (one full pass), the outer loop checks the flag's status.

If swapped == true: This means at least one swap occurred. The array might not be fully sorted yet, so the outer loop continues to the next pass (e.g., i increments) and resets the flag to false for the new pass.

If swapped == false: This is the key. If the flag is still false, it means the inner loop went through the entire array and didn't find a single pair to swap. This is the signal that the array is perfectly sorted. The if (swapped == false) condition becomes true, and the break; statement executes.

This early termination immediately halts the bubbleSort function, preventing it from running any more unnecessary passes and comparisons on an already sorted list. This optimization doesn't change the worst-case scenario, but it dramatically improves the best-case scenario (an already-sorted array) to O(n).