Bubble Sort

Logic

• At every ith pass(1....n-1) , we compare each pair of adjacent n-i+1 elements and swap them if they are in wrong order.

• Each pass places the next largest element in its proper place.After end of every ith pass , last i elements are placed in their proper place. 

• Repeat the process till all elements in the array are sorted.

No of passes required = n - 1

No of comparisons required in ith pass = n - i 

Example 

Lets sort  5  3  2  1  4 using bubble sort.

Pass 1    
          5  3  2  1  4             Compare 5 and 3

          3  5  2  1  4             Compare 5 and 2

          3  2  5  1  4             Compare 5 and 1

          3  2  1  5  4             Compare 5 and 4

          3  2  1  4  5             5 placed in its place

Pass 2
          3  2  1  4  5             Compare 3 and 2

          2  3  1  4  5             Compare 3 and 1

          2  1  3  4  5             Compare 3 and 4

          2  1  3  4  5             4 and 5 placed in their places


Pass 3
          2  1  3  4  5             Compare 2 and 1

          1  2  3  4  5             Compare 2 and 3

          1  2  3  4  5             3 , 4 and 5 placed in their places  

Pass 4 
          1  2  3  4  5             Compare 1 and 2

          1  2  3  4  5             2 , 3 , 4 and 5 placed in their places

Code 

#include<stdio.h>

void bubble_sort(int[],int);

int main()
{
    int a[15],n,i;

    printf("\n Enter no of elements ");
    scanf("%d",&n);

    printf("\n Enter elements ");

    for(i=0;i<n;i++)
        scanf("%d",&a[i]);

    bubble_sort(a,n);

    return 0;
}

void bubble_sort(int a[],int n)
{
    int i,j,temp;

    for(i=0;i<n-1;i++)
    {
        for(j=0;j<n-i-1;j++)
        {
            if(a[j]>a[j+1])
            {
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }

    printf("\n Sorted elements");

    for(i=0;i<n;i++)
        printf(" %d",a[i]);
}

O/P

More 

Time Complexity of bubble sort