BUBBLE SORT

Bubble sort is the simplest sorting algorithm, with complexity = O(n^2), both for average case and for worst case. Bubble sort is a comparison sort that compares successive elements, and then swaps them, if a condition is satisfied.

WORKING OF BUBBLE SORT :-

Consider the example,"6 1 5 2 9", and sort the array from lowest number to greatest number using bubble sort. In each step, elements written in bold are being compared.

First Pass:
( 6 1 5 2 9 ) ->( 1 6 5 2 9 ), Here, algorithm compares the first two elements, and swaps since 6 > 1.
( 1 6 5 2 9 ) ->( 1 5 6 2 9 ), Swap since 6 > 5
( 1 5 6 2 9 ) ->( 1 5 2 6 9 ), Swap since 6 > 2
( 1 5 2 6 9 ) ->( 1 5 2 6 9 ), Now, since these elements are already in order (9 > 6), algorithm does not swap them.
Second Pass:
( 1 5 2 6 9 ) ->( 1 5 2 6 9 ), No swap
( 1 5 2 6 9 ) ->( 1 2 5 6 9 ), Swap since 5 > 2
( 1 2 5 6 9 ) ->( 1 2 5 6 9 ), No swap
( 1 2 5 6 9 ) ->( 1 2 5 6 9 ), No swap
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
( 1 2 5 6 9 ) ->( 1 2 5 6 9 ), No swap
( 1 2 5 6 9 ) ->( 1 2 5 6 9 ), No swap
( 1 2 5 6 9 ) ->( 1 2 5 6 9 ), No swap
( 1 2 5 6 9 ) ->( 1 2 5 6 9 ), No swap

We can make the bubble sort efficient, by breaking through the outer for loop, if the control never goes under the if condition in the inner for loop.

Even in the best, case this sorting algorithm will compare as that of the best case. So this algorithm is inefficient.

#include<stdio.h>

void bubbleSort(int arr[],int n)
{
    int i,j,temp;
    for(i=0;i<n-1;i++)
    {
        for(j=0;j<n-1-i;j++)
        {
            if(arr[j]>arr[j+1])
            {
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
}
void bubbleSortImproved(int arr[],int n)
{
    int i,j,temp,flag=0;
    for(i=0;i<n-1;i++)
    {
        flag=0;
        for(j=0;j<n-1-i;j++)
        {
            if(arr[j]>arr[j+1])
            {
                flag=1;
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
        if(flag==0)
            break;
    }
}
void bubbleSortIndexed(int arr[],int a,int b) // sorting subArray from arr[a] to arr[b]
{
    int i,j,temp,n;
    n=b-a+1; // number of elements to be sorted
    for(i=0;i<n-1;i++)
    {
        for(j=a;j<b-i;j++)
        {
            if(arr[j]>arr[j+1])
            {
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
}

void bubbleSortImprovedIndexed(int arr[],int a,int b) // sorting subArray from arr[a] to arr[b]
{
    int i,j,temp,flag,n;
    n=b-a+1; // number of elements to be sorted
    for(i=0;i<n-1;i++)
    {
        flag=0;
        for(j=a;j<b-i;j++)
        {
            if(arr[j]>arr[j+1])
            {
                flag=1;
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
        if(flag==0)
            break;
    }
}

int main()
{
    int arr[]={3,8,1,23,7,9,24,6,12};
    int n=9,i;
    bubbleSortImprovedIndexed(arr,3,6);
    //bubbleSort(arr,n);
    for(i=0;i<n;i++)
        printf("%d\n",arr[i]);
}