Optimized Bubble Sort

Bubble sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. Here is an optimized version of the bubble sort algorithm in C++:

Start by initializing a flag variable swapped to indicate whether any swaps have been made in a pass. Set it to true.
Create a for loop that runs until the swapped flag is true. This loop will iterate over the array elements.
Inside the loop, set the swapped flag to false at the beginning of each pass. This assumes that no swaps will be made in the current pass, until proven otherwise.
Create another for loop that runs from the first element to the last element minus the current iteration count. This loop will compare adjacent elements and swap them if they are in the wrong order.
Inside the second loop, check if the current element is greater than the next element. If it is, swap the elements and set the swapped flag to true to indicate that a swap has been made.
After the second loop finishes, check if the swapped flag is still false. If it is, it means no swaps were made in the current pass, and the array is already sorted. In this case, break out of the first loop.
Repeat steps 2 to 6 until the array is completely sorted (i.e., no swaps are made in a pass).

Here is the code implementation of the optimized bubble sort algorithm in C++:

void bubbleSort(int arr[], int n) {
    bool swapped;
    for (int i = 0; i < n-1; i++) {
        swapped = false;
        for (int 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;
    }
}

This optimized version of the bubble sort algorithm reduces the number of passes needed to sort the array by breaking out of the loop if no swaps are made in a pass. This can significantly improve the efficiency of the sorting process.