C program to implement optimized bubble sort

Optimized bubble sort implementation: In this tutorial, we will learn how to implement optimized bubble sort using C program? By Sneha Dujaniya Last updated : August 03, 2023

Bubble Sort is a simple, stable, and in-place sorting algorithm. Due to its simplicity, it is widely used as a sorting algorithm by computer programmers.

The basic working principle of a simple bubble sort is that it repeatedly swaps the adjacent elements if they are in the wrong order. Hence, after every full iteration, the largest element reaches its position as in the sorted array.

However, this simple bubble sort has time complexity O(n^2) in all cases because the inner loop runs even if the array is sorted. Therefore, we use an optimized version of bubble sort. This version uses a bool variable to check whether any swap took place in the previous iteration. If yes, only then the next iteration takes place. If no, then the loop breaks.

Pseudo code

1.	for i: 0 to n-1 not inclusive do:
2.	     swapped = false
3.	     for j: 0 to n-i-1 not inclusive do:
4.	          If a[j] > a[j+1] then
5.	                   swap a[j] and a[j+1]
6.	                   swapped = true
7.	          end if
8.	     end for
9.	     if swapped == false then
10.	            break
11.	     end if
12.	end for

Example with explanation

Input Array: 
5 8 1 2 9
Here, I will run from 0 to 3
Since, i < n-1 => i < 5-1 => i < 4

Iteration 1 (i = 0):
For j = 0, (5 8 1 2 9) -> (5 8 1 2 9) No swaps because 5 < 8
For j = 1, (5 8 1 2 9) -> (5 1 8 2 9), swap because 1 < 8
For j = 2, (5 1 8 2 9) -> (5 1 2 8 9), swap because 2 < 8
For j = 3, (5 1 2 8 9) -> (5 1 2 8 9), no swap
1^st Pass gives – 5 1 2 8 9

Iteration 2 (i = 1):
For j = 0, (5 1 2 8 9) -> (1 5 2 8 9) No swap because 1 < 5
For j = 1, (1 5 2 8 9) -> (1 2 5 8 9), swap because 2 < 5
For j = 2, (1 2 5 8 9) -> (1 2 5 8 9), no swap
2^nd Pass gives – 1 2 5 8 9

Iteration 3 (i = 2):
For j = 0, (1 2 5 8 9) -> (1 2 5 8 9), No swap because 1 < 2
For j = 1, (1 2 5 8 9) -> (1 2 5 8 9), No swap 2 < 5
3^rd Pass gives – 1 2 5 8 9

Here, the 4^th iteration won't take place since the 
loop break because there was no swapping 
in the third iteration.

Time complexity

The time complexity of Binary Search can be described as: T(n) = T(n/2) + C

Worst case: O(n^2)
Average Case: O(n^2)
Best case: O(n), if the array is already sorted
Space Complexity: O(1)

C program to implement optimized bubble sort

#include <stdio.h>

void swap(int* x, int* y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

void bubble_sort(int arr[], int n)
{
    int i, j;
    bool swapped;
    for (i = 0; i < n - 1; i++) {
        swapped = false;
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
                swapped = true;
            }
        }
        if (swapped == false)
            break;
    }
}

int main()
{
    int arr[] = { 12, 46, 34, 82, 10, 9, 28 };
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("\nInput Array: \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
        
    bubble_sort(arr, n);

    printf("\nSorted Array: \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}

Output

Input Array:
12 46 34 82 10 9 28
Sorted Array:
9 10 12 28 34 46 82