1. Bubble Sort

Idea:

Repeatedly swap adjacent elements if they are in wrong order → Largest element “bubbles” to the end each pass

Complexity:

• Worst: O(n²)
• Best (with optimization): O(n)
• Space: O(1)

void bubbleSort(int arr[], int n)
{
    for(int i=n-1;i>0;i--){
        bool swapped = false;
        for(int j=0;j<i;j++){
            if(arr[j]>arr[j+1]){
                swap(arr[j],arr[j+1]);
                swapped = true;
            }
        }
        if(!swapped) break;
    }
}

⚡ Optimization (IMPORTANT):

If no swaps in a pass → array already sorted → break early

👉 This is what theswapped flag does

2. Selection Sort

Idea:

Pick the smallest element from unsorted part → place it at correct position (i)

Complexity:

• Best: O(n²)
• Worst: O(n²)
• Space: O(1)