Bubble sort

Introduction:

This is a comparison based sort where we compare pair of adjacent elements every time and move the larger element to right of the array.

Problem Statement:

Sort an array of n integers

Algorithm

1. we have an array of n numbers.

2. In this method we bubble large numbers to right side.... ( to get sorted array in ascending order )

3. In first iteration we compare adjacent numbers and swap larger to right.

i.e., for i = 0 to n-1 if a[i] > a[i+1] then swap(a[i], a[i+1]) after this iteration we see that the largest number in the array will be at the right end.

4. Now repeat the above iteration again with one less array size ...we will see that second largest will be at the second position from the end ...

5. we repeat the above step untill array size is 0

6. After all iterations the array will be sorted.

Pseudo code :

bubble_sort(a[], n):
    i = n-1
    while i > 0:  // sort the sub array[0..i]
        j = 0
        while j < i:
            if a[j] > a[j+1]: // push bigger number towards right
                swap(a[j], a[j+1])
            j++
        i--  // decrease size of array as the last element a[i] is biggest.

Code :

    #include <bits/stdc++.h>
    using namespace std;
    
    void bubble_sort(int a[], int n)
    {
        int i = n - 1; // array size i
        while (i > 0)
        {
            int j = 0;
            while (j < i) // bubble sort array from j= 0 to i
            {
                if (a[j] > a[j + 1]) // bubble up
                {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
                j++;
            }
            i--;
        }
    }
    
    int main()
    {
        int n;
        cout << "Enter n: ";
        cin >> n;
        int a[n];
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        bubble_sort(a, n);
        for (int i = 0; i < n; i++)
        {
            cout << a[i] << " ";
        }
        printf("\n");
    }

Complexity Analysis :

best case : \(O(n)\) when array is already sorted

worst case \(O(n^2)\) when array is reverse sorted

So complexity lies between these two extremes.