Home » C/C++ Data Structure programs

C program to implement Optimized Bubble Sort

Optimized Bubble Sort Algorithm: Here, we are going to learn about the optimized bubble sort algorithm, how it works, and C language implementation of the optimized bubble sort.
Submitted by Sneha Dujaniya, on June 19, 2020

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:

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

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

Optimized Bubble Sort Implementation:

#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