Bubble Sort

 Bubble Sort is a sorting algorithm and this algorithm is used to sort (arranging the elements in ascending or descending order) arrays/list.

Application

Understand the working of Bubble sort

• Bubble sort is mainly used in educational purposes for helping students understand the foundations of sorting.
• This is used to identify whether the list is already sorted. When the list is already sorted (which is the best-case scenario), the complexity of bubble sort is only O(n).
• In real life, bubble sort can be visualized when people in a queue wanting to be standing in a height wise sorted manner swap their positions among themselves until everyone is standing based on increasing order of heights.

Algorithm:

ALGORITHM bubble_sort(a[], size){

    for(i=size-1;i>0;i--){

        for(j=0;j<size-1;j++){

            //when adjacent nodes have greater value

            if(a[j] > a[j+1]{

                swap(a[j],a[j+1]);

            }

        }//end of child for loop

    }//end of parent for loop

}//end of bubble_sort function

Pseudo Code:

#include<iostream>

using namespace std;

void bubble_sort(int a[],int size){

    bool is_swapped = false;

       

    for(int i=size-1;i>0;i--){

        for(int j=0;j<i;j++){

            //check whether the fist element is bigger or not

            if(a[j] > a[j+1]){

                swap(a[j],a[j+1]);

                is_swapped = true;

            }

        }

        if(! is_swapped){

            break;

        }

    }

}

void print_array(int a[],int size){

    for(int i=0;i<size;i++){

        cout<<a[i]<<"\t";

    }

    cout<<endl;

}

int main(){

    int size = 10;

    int a[size] = {3,20,22,23,29,34,44,83,90,99};

    /**

     * sorted array of {34,23,44,90,29,20,3,99,83,22};

     * a = {3,20,22,23,29,34,44,83,90,99};

     *index 0  1  2  3  4  5  6  7  8  9

     */

    cout<<"Before sorting array: "<<endl;

    print_array(a,size);

    cout<<"After sorting array: "<<endl;

    bubble_sort(a,size);

    print_array(a,size);

    return 0;

}

Complexity:

Best Case          : O(n)

Worse Case       : O(n²)

Average Case    : O(n²)

Space                : O(n)

Auxiliary Space : 1 (no auxiliary space)