Bubble Sort

Bubble sort is one of the simplest sorting algorithm where we essentially bubble up the largest element to its appropriate position. It does n iteration and in each iteration we check the two adjacent elements and if they are not sorted we swap them. Since this bubbles up the largest element at the end, after i iterations i elements are sorted so we only need to iterate over n - i elements in the next iteration.

Since we are iterating n times over the input and comparing two adjacent elements in each iteration, therefore the complexity would be O(n^2).

Since we are not using any extra space other than input itself, therefore the space complexity is O(1). Bubble sort is therefore called an in-place sorting algorithm.

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