Bubble Sort | Notion

void bubbleSort(vector<int>& arr, int n) {
    for(int i= 0 ; i<=n-2 ; i++){
        for(int j=0 ; j<=n-2-i ; j++){
            if(arr[j] > arr[j+1]){
                swap(arr[j], arr[j+1]);
            }
        }
    }
}

Bubble Sort Analysis Table

Type	Complexity	Explanation
Time (Best)	`O(n)`	Array already sorted, inner loop makes no swaps (with flag)
Time (Average)	`O(n²)`	Elements swapped multiple times on average
Time (Worst)	`O(n²)`	Reverse sorted array, every pair must be swapped
Space	`O(1)`	In-place sorting, no extra memory used
Stable?	Yes	Equal elements do not change order (as long as swap is used carefully)
Used in	Simple learning, small datasets, teaching sorting basics