Your Success, Our Mission!

6000+ Careers Transformed – Be Next!

Your Success, Our Mission!

6000+ Careers Transformed.

Course Outline

Early Termination Optimization

Last Updated: 12th August, 2026

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, "Nope, 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).

Module 5: Optimizing Bubble Sort