In the bubble sort algorithm, comparisons are made even when the array is already sorted. Because of that, the execution time increases.

To solve it, we can use an extra variable swapped. It is set to true if swapping requires; otherwise, it is set to false.

It will be helpful, as suppose after an iteration, if there is no swapping required, the value of variable swapped will be false. It means that the elements are already sorted, and no further iterations are required.

This method will reduce the execution time and also optimizes the bubble sort.

Algorithm

        bubbleSort(array)  
        n = length(array)  
        repeat  
            swapped = false  
            for i = 1 to n - 1  
                    if array[i - 1] > array[i], then  
                    swap(array[i - 1], array[i])  
                    swapped = true  
                    end if  
            end for  
            n = n - 1  
        until not swapped  
        end bubbleSort 

Program using C

//OPTIMIZED BUBBLE SORT #include <stdio.h> // Function for bubble sorting void bubbleSortExample(int arr[], int n){ for (int i = 0; i < n - 1; ++i){ int Swap = 0; // Comparing array elements for (int x = 0; x < n - i - 1; ++x){ if (arr[x] > arr[x + 1]){ int temp = arr[x]; arr[x] = arr[x + 1]; arr[x + 1] = temp; Swap = 1; } } if (Swap == 0){ // No swapping required break; } } } void displayArray(int arr[], int n){ for (int x = 0; x < n; ++x){ printf("%d ", arr[x]); } printf("\n"); } // Driver method int main(){ int data[] = {27, 13, -54, 93, -20}; // finding array's length int n = sizeof(data) / sizeof(data[0]); bubbleSortExample(data, n); printf("Array after implementing bubble sort: \n"); displayArray(data, n); }