Bubble Sort

Intuition

This works as follow, you iterate through the array and check two adjacent elements if the second one is smaller you swap them, in this way the largest number will be at the end of array after first iteration. In second iteration you do the same till the second last element of array, and so on. Also keep a flag to check if any swaps are made in some iteration, if no swaps are made you can stop as the array is already sorted.

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

void bubble_sort(vector<int>& a) {
  for (int i = 0; i < a.size(); i++) {
    bool swap = false;
    for (int j = 0; j < a.size() - i - 1; j++) {
      if (a[j + 1] < a[j]) {
        int temp = a[j + 1];
        a[j + 1] = a[j];
        a[j] = temp;
        swap = true;
      }
    }
    if (!swap) {
      break;
    }
  }
}

int main() {
  vector<int> a = {1, 4, 2, 5, 5, 6, 3, 3, 4};
  bubble_sort(a);
  for (auto i : a) cout << i << " ";
  return 0;
}

Analysis

• Time complexity
  • Best: \(O(n)\), if the array is sorted
  • Average: \(O(n^2)\)
  • Worst: \(O(n^2)\)
• Space complexity - \(O(1)\)