Bubble Sort Program

 

Bubble  sort is most popular sorting technique because it is very simple to understand and implement. The algorithm achieves its name from the fact that,with each iteration the largest value moves like a bubble to the top of the array. The bubble sort method is not efficient for large arrays.

 

 

The bubble sort work as follows:

If N elements are given in memory then for sorting we do following steps:

                1.First  compare the 1st and 2nd element of the array. If 1st<2nd , then no interchange else interchange 1st and 2nd elements.

                2.Now compare 2nd and 3rd. If 2nd >3rd then interchange the value of 2nd and 3rd. Otherwise no interchange.

                3.Now compare 3rd with 4th elements, if 3rd>4th then interchange the value of 3rd and 4th, otherwise no interchange.

                4.Similarly compare until N-1TH elements is compared with  Nth elements.

                5.At the end, the highest element value is reached at the Nth place.

                6.Now elements will be copared until N-1 passes.

 In every pass ,one element is reached at the end. So, if number of elements in N, then it takes N-1 passes to sort the N elements. Let us take the elements 28,20,30,15 and 05 end illustrate the same. Here N=5,

A[5]

A[0]=28;

A[1]=20;

A[2]=30;

A[3]=15;

A[4]=05;

Pass 1:

       The comparison for pass1 are as follows.

                Compare A[0] and A[1]. Since 28>20, interchange them.

                Compare A[1] and A[2]. since 28<30, no change .

                Compare A[2] and A[3]. Since 30>15 interchange them.

                Compare A[3] and A[4]. Since 30>05, interchange them.

At the end of first pass, the largest element of the array 30 is bubbled up to the last position in the array

Answer is ……….A[5];

A[0]=20;

A[1]=28;

A[2]=15;

A[3]=05;

A[4]=30;     //largest element

Pass 2:

The comparison for pass2 are as follows:

                Compare A[0] and A[1]. Since 20<28, no change

                Compare A[1] and A[2]. since 28>15, interchange them

                Comare A[2] and A[3]. Since 28>05 interchange them.

Answer is………….A[5];

A[0]=20;

A[1]=15;

A[2]=05;

A[3]=28;      //second largest

A[4]=30;     //largest element

At  the end of pass2, the second largest element of the array, 28 is bubbled upto the 3rd position in the array.

Pass 3:

The comparison for pass3 are as follows.

                Compare A[0] and A[1]. Since 20>15, no change

                Compare A[1] and A[2]. since 20>05, interchange them

Answer is……A[5];

A[0]=15;

A[1]=05;

A[2]=20;        //third largest

A[3]=28;      //second largest

A[4]=30;     //largest element

At the end of 3rd pass , the third largest element 20 is bubbled up to the 2nd position in the array.

Pass 4:

The comparison for pass4 is as follows.

                Compare A[0] and A[1]. Since 15>05, interchange them

Answer……..A[5];

                                                SORTED ARRAY

A[0]=05;

A[1]=15;

A[2]=20;        //third largest

A[3]=28;      //second largest

A[4]=30;     //largest element

If number of elements is 5, then at the end of 4th pass the array elements are in sorted order. In every pass, number of comparisons are decremented. i.e.,

1st pass …4 comparison

2nd pass…3 comparison

3rd pass…2 comparison

4th pass…1 comparison.

For(j=0;j<=n-pass-1;j++)

  {

                If(a[j]>a[j+1])

                                {

                                                Temp=a[j];

                                                A[j]=a[j]+1;

                                                A[j+1]=temp;

                                }

}

When pass=1, j ranges from  0 to (5-1-1) i.e. 0 to 3. So 4 comparisons take place

When pass=2, j ranges from 0 to (5-2-1)i.e, 0 to 2. So 3 comparisons take place

When pass=3 j ranges from 0 to (5-3-1)i.e , 0 to 1. So 2 comparisons take place

When pass=4 j ranges from 0 to (5-4-1)i.e, 0 to 0 .So 1 comparison takes place

As the value of pass is varying from 1 to (n-1), the value of comparisons from (n-1) to 1 respectively.

//Program to sort ‘n’ number using Bubble Sort

#include<stdio.h>

#include<conio.h>

void bubble_sort(int [],int);

void main()

{

                int i,j,a[20],n,temp;

                clrscr();

                printf("\n Enter the number of elements");

                scanf("%d",&n);

                printf("Enter the array elements");

                for(i=0;i<n;i++)

                     scanf("%d",&a[i]);

                bubble_sort(a,n);   //calling function

                printf("\n The sorted elements are....\n");

                for(i=0;i<n;i++)

                     printf("%d"a[i]);

                getch();

}

//Function to sort n elements using Bubble Sort

void bubble_sort(int a[],int n)

{

                int pass,temp,j;

                for(pass=1;pass<n;pass++)

                     {

                                for(j=0;j<=n-pass-1;j++)

                                     {

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

                                                    {

                                                                temp=a[j];

                                                                a[j]=a[j+1];

                                                                a[j+1]=temp;

                                                     }

                                     }

                     }

}

Bubble Sorting using function

//Second Example

/* Program of sorting using bubble sort */

#include <stdio.h>

#define MX 20

void main()

{

                int arr[MX],ii,jj,k,temp,lnum,exchanges;

                printf("Enter the number of elements : ");

                scanf("%d",&lnum);

                for (ii = 0; ii < lnum; ii++)

                {

                                printf("Enter element %d : ",ii+1);

                                scanf("%d",&arr[ii]);

                }

                printf("Unsorted list is :\n");

                for (ii = 0; ii < lnum; ii++)

                                printf("%d ", arr[ii]);

                 printf("\n");

                /* Bubble sort*/

                for (ii = 0; ii < lnum-1 ; ii++)

                {

                                exchanges=0;

                                for (jj = 0; jj <lnum-1-ii; jj++)

                                {

                                                if (arr[jj] > arr[jj+1])

                                                {

                                                                temp = arr[jj];

                                                                arr[jj] = arr[jj+1];

                                                                arr[jj+1] = temp;

                                                                exchanges++;

                                                }/*End of if*/

                                }/*End of inner for loop*/

                                if(exchanges==0) /*If list is sorted*/

                                                break;

                                printf("After Pass %d elements are :  ",ii+1);

                                for (k = 0; k < lnum; k++)

                                                printf("%d ", arr[k]);

                                printf("\n");

                }/*End of outer for loop*/

                printf("Sorted list is :\n");

                for (ii = 0; ii < lnum; ii++)

                                printf("%d ", arr[ii]);

                printf("\n");

}/*End of main()*/

Bubble Sorting

Efficiency:

In bubble sort, n-1 comparisons are made in pass1, n-2 in pass2, n-3 in pass3 ans so on. Let F(n) be the complexity function.

Total number of comparisons=F(n)=(n-1)+(n-2)+(n-3)+………+3+2+1.

It is in the form of arithmetic progression series. So we can apply the formula

Sn=n/2[2a+(n-1)d]

Where n=number of elements in a series.Here it is(n-1).

            a=first element in series.Here it is 1.

            d=difference between second element and first element.Here it is 1.

Sn =(n-1)/2[2*1+(n-1-1)*1]

     =(n-1)/2[2+n-2]

     =n(n-1)/2

Where is of 0(n2).