Bubble Sort

About

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

void print(int a[], int n)
{
  for (int i = 0; i < n; i++)
  {
    cout << a[i] << " ";
  }
  cout << endl;
}
// BubbleSort
void BubbleSort(int a[], int n)
{
  for (int i = 0; i < n; i++)
  {
    bool flag = false;
    for (int j = 0; j < n - 1; j++)
    {
      if (a[j] > a[j + 1])
      {
        flag = true;
        int temp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = temp;
      }
    }
    if (!flag)
        break;
  }
  print(a, n);
}
signed main(){
  int n;
  cin >> n;
  int a[n];
  for (int i = 0; i < n; i++)
  {
    cin >> a[i];
  }
  BubbleSort(a, n);
  print(a, n);
  return 0;
}

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst case time complexity is quite high.

How Does it Work?

Consider an array arr[] = 5, 1, 4, 2, 8

First Pass: Bubble sort starts with very first two elements, comparing them to check which one is greater.
- ( 5 1 4 2 8 ) -> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
- ( 1 5 4 2 8 ) -> ( 1 4 5 2 8 ), Swap since 5 > 4
- ( 1 4 5 2 8 ) -> ( 1 4 2 5 8 ), Swap since 5 > 2
- ( 1 4 2 5 8 ) -> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
Second Pass: Now, during second iteration it should look like this:
- ( 1 4 2 5 8 ) -> ( 1 4 2 5 8 )
- ( 1 4 2 5 8 ) -> ( 1 2 4 5 8 ), Swap since 4 > 2
- ( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
- ( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
Third Pass: Now, the array is already sorted, but our algorithm does not know if it is completed. and it needs one whole pass without any swap to know it is sorted.
- ( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
- ( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
- ( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
- ( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )

Time Complexity

Worst Case Time Complexity is: O(n^2)
Average Case Time Complexity is: Ω(n^2)
Best Case Time Complexity is: Ω(n)