Bubble Sort is a simple and intuitive sorting algorithm with limited practical use for large datasets but serves as a good starting point for understanding sorting algorithms.

The thing that we have to keep in mind is to repeatedly swap the adjacent elements if they are in the wrong order

1. Time Complexity:

   • Worst Case: O(n^2) - Occurs when the input array is in reverse order, and each element needs to be compared and swapped in every pass through the array.

   • Best Case: O(n) - Occurs when the input array is already sorted. However, the algorithm still needs to make passes through the array to ensure it is sorted.

   • Average Case: O(n^2) - On average, it performs worse than more advanced sorting algorithms like Merge Sort or Quick Sort.

2. Space Complexity:

   • Bubble Sort is an in-place sorting algorithm, meaning it doesn't require additional memory for sorting and operates directly on the input array.

3. Stability:

   • Bubble Sort is a stable sorting algorithm. Stable sorting algorithms maintain the relative order of equal elements in the sorted output as they were in the input.

4. Adaptability:

   • Bubble Sort is adaptive. In the context of sorting algorithms, "adaptive" means that the time complexity improves when the input is partially ordered. Bubble Sort can be more efficient on partially sorted data compared to its worst-case time complexity.

#include<bits/stdc++.h>
using namespace std;

void bubbleSort(int arr[],int n){
    for(int i = 0; i<n-1; i++){
        for(int j = 0; j<n-i-1; j++)
        {
            // compare adjecent element
            if(arr[j]>arr[j+1]){
                // swap if they are in a wrong order
                swap(arr[j],arr[j+1]);
            }
        }
    }
}

void printArray(int arr[],int size){
    for(int i =0; i<size; i++){
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}

int main(){
    int InputArray[] = {9,1,5,4,2,7};
    int sizeofInputArray = sizeof(InputArray) / sizeof(InputArray[0]);

    cout << "Original array: ";
    printArray(InputArray, sizeofInputArray);

    // calling the funtion
    bubbleSort(InputArray,sizeofInputArray);

    // Printing the array in a sorted way
    cout<<"Sorted Array:";
    printArray(InputArray,sizeofInputArray);

    return 0;
}

for (int j = 0; j < n - i - 1; j++): This loop is responsible for iterating through the array elements up to the unsorted portion. The n - i - 1 limit is used because after each pass through the outer loop (for (int i = 0; i < n - 1; i++)), the largest unsorted element gets moved to its correct position at the end of the array. So, we don't need to compare and swap it again in subsequent passes.

if (arr[j] > arr[j + 1]) {: This condition checks whether the current element (arr[j]) is greater than the next element (arr[j + 1]). If this condition is true, it means that the two adjacent elements are in the wrong order and need to be swapped.

swap(arr[j], arr[j + 1]);: If the condition in the if statement is true, the swap function is called to interchange the values of arr[j] and arr[j + 1], effectively putting them in the correct order.

Thank you for reading my content. Be sure to follow and comment on what you want me to write about next 🤓