Bubble Sort

Approach: We compare all the elements for 0 to n-1 Sort the array from back

#include <iostream>
#include <vector>
 
using namespace std;
 
void BubbleSort (vector<int> &arr, int n)
{
   for (int i = 0; i < n - 1; ++i)
   { 
      bool swapped = false;
      for (int j = 0; j < n - i - 1; ++j)
      {
         if (arr[j] > arr[j+1]) //check if adjacent element is
                      //not in order
         {
            swap(arr[j], arr[j + 1]);
            swapped = true;
         }
      }
      // Value at n-i-1 will be maximum of all the values below this index.

      if(!swapped)
         break;
   } 
} 
 

Time Complexity: O(n ^ 2)