Bubble Sort

This video is good to help:

I have also taken help from DS Made Easy by Karumanchi book to find the algo pesudocode.

Pseudocode:

void bubbleSort(int *arr,int n)
{
    int pass,j;
    for(pass=n-1; pass>=0;  pass--)
    {
        for(j=0; j<=pass-1; j++)
        {
            if(arr[j]>arr[j+1])
            {
                swaps(&arr[j],&arr[j+1]);
            }
        }
    }
}

Implementation:

#include<bits/stdc++.h>
using namespace std;
int swaps(int *p,int *q)
{
    int temp=*q;
    *q=*p;
    *p=temp;
}
void bubbleSort(int *arr,int n)
{
    int pass,j;
    for(pass=n-1; pass>=0;  pass--)
    {
        for(j=0; j<=pass-1; j++)
        {
            if(arr[j]>arr[j+1])
            {
                swaps(&arr[j],&arr[j+1]);
            }
        }
    }
}

void printArray(int *arr,int n)
{
    for(int i=0; i<n; i++)
    {
        cout<<arr[i]<<" ";
    }
}

int main()
{
    int A[]= {2,7,19,1,5,9};
    int n=sizeof(A)/sizeof(A[0]);
    bubbleSort(A,n);
    printArray(A,n);
}

I need to improve this algorithm as it is not passing all the sizes of array so there will be some vacant position in array which increases the complexity in the running time so we need to out of the loop when it has nothing to swap, so our improvised algorithm will be:

Pseudocode:

void bubbleSort(int *arr,int n)
{
    int pass,j,flag=0;
    for(pass=n-1; pass>=0;  pass--)
    {
        flag=0;
        for(j=0; j<=pass-1; j++)
        {
            if(arr[j]>arr[j+1])
            {
                swaps(&arr[j],&arr[j+1]);
                flag=1;
            }
        }
        if(flag==0)
            break;
    }
}

Implementation:

#include<bits/stdc++.h>
using namespace std;
int swaps(int *p,int *q)
{
    int temp=*q;
    *q=*p;
    *p=temp;
}
void bubbleSort(int *arr,int n)
{
    int pass,j,flag=0;
    for(pass=n-1; pass>=0;  pass--)
    {
        flag=0;
        for(j=0; j<=pass-1; j++)
        {
            if(arr[j]>arr[j+1])
            {
                swaps(&arr[j],&arr[j+1]);
                flag=1;
            }
        }
        if(flag==0)
            break;
    }
}

void printArray(int *arr,int n)
{
    for(int i=0; i<n; i++)
    {
        cout<<arr[i]<<" ";
    }
}

int main()
{
    int A[]= {2,7,19,1,5,9};
    int n=sizeof(A)/sizeof(A[0]);
    bubbleSort(A,n);
    printArray(A,n);
}

This below video can help for better optimization that implemented in the above code:

Time Complexity in Running Time:

Worst Case: O(n^2)
BEst Case without improve: O(n^2)
Best Case(Improvised): O(n)
Average Case: O(n^2)
Space Complexity: O(1)
Simulation Tried to be drawn by me: