8.8 – Bubble Sort

by subbu on October 29, 2013

Bubble sort:

It is another simple way of sorting elements in an array. The basic procedure of bubble sort is to navigate the array sequentially several times. In each pass, we compare each element (a[i]) with its next element (a[i+1]) and interchange them when the next element is less than the current element (a[i+1]<a[i]).

Let me explain the algorithm with few elements

25      20      22      11      8        18

Pass 1:
We compare a[i] with a[i+1] for i=0, 1, 2, 3 and 4, and we interchange when a[i+1]<a[i].

25      20      22      11      8        18

When i is 0 then a[i+1]<a[i] (20<25) is true, hence they are interchanged

20      25      22      11      8        18

When i is 1 then a[i+1]<a[i] (22<25) is true, hence they are interchanged

20      22      25      11      8        18

When i is 2 then a[i+1]<a[i] (11<25) is true, hence they are interchanged

20      22      11      25      8        18

When i is 3 then a[i+1]<a[i] (8<25) is true, hence they are interchanged

20      22      11      8        25      18

When i is 4 then a[i+1]<a[i] (18<25) is true, hence they are interchanged

20      22      11      8        18      25

Here the maximum element of array (25) reached to the end of array as a bubble. The above iteration can be summarized using a loop

for(i=0;i<=4;i++)
  if(a[i+1]<a[i])
  {
    temp=a[i];
    a[i]=a[i+1];
    a[i+1]=temp;
  }

Pass 2:
We compare a[i] with a[i+1] for i=0, 1, 2 and 3, and we interchange when a[i+1]<a[i].

20      22      11      8        18      25

When i is 0 then a[i+1]<a[i] (22<20) is false, hence the array is unchanged

20      22      11      8        18      25

When i is 1 then a[i+1]<a[i] (11<22) is true, hence they are interchanged

20      11      22      8        18      25

When i is 2 then a[i+1]<a[i] (8<22) is true, hence they are interchanged

20      11      8        22      18      25

When i is 3 then a[i+1]<a[i] (18<22) is true, hence they are interchanged

20      11      8        18      22      25

Here the maximum element of array from a[0] to a[4] (22) reached to the end of array as a bubble. The above iteration can be summarized using a loop

for(i=0;i<=3;i++)
  if(a[i+1]<a[i])
  {
    temp=a[i];
    a[i]=a[i+1];
    a[i+1]=temp;
  }

Pass 3:
We compare a[i] with a[i+1] for i=0, 1 and 2, and we interchange when a[i+1]<a[i].

20      11      8        18      22      25

When i is 0 then a[i+1]<a[i] (11<20) is true, hence they are interchanged

11      20      8        18      22      25

When i is 1 then a[i+1]<a[i] (8<20) is true, hence they are interchanged

11      8        20      18      22      25

When i is 2 then a[i+1]<a[i] (18<20) is true, hence they are interchanged

11      8        18      20      22      25

Here the maximum element of array from a[0] to a[3] (20) reached to the end of array as a bubble. The above iteration can be summarized using a loop

for(i=0;i<=2;i++)
  if(a[i+1]<a[i])
  {
    temp=a[i];
    a[i]=a[i+1];
    a[i+1]=temp;
  }

Pass 4:
We compare a[i] with a[i+1] for i=0 and 1, and we interchange when a[i+1]<a[i].

11      8        18      20      22      25

When i is 0 then a[i+1]<a[i] (8<11) is true, hence they are interchanged

8        11      18      20      22      25

When i is 1 then a[i+1]<a[i] (18<11) is false, hence the array is unchanged

8        11      18      20      22      25

Here the maximum element of array from a[0] to a[2] (18) is at its position. The above iteration can be summarized using a loop

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

Pass 5:
We compare a[i] with a[i+1] for i=0, and we interchange when a[i+1]<a[i].

8        11      18      20      22      25

When i is 0 then a[i+1]<a[i] (11<8) is false, hence the array is unchanged

Logic:

Bubble sort operations

In all the above navigation steps, a common loop is used to send the maximum element to its position

for(i=0;i<=?;i++)   /* ? varies pass to pass */
  if(a[i+1]<a[i])
  {
    temp=a[i];
    a[i]=a[i+1];
    a[i+1]=temp;
  }

During the first pass navigated from 0 to 4 (6-2), during the second pass navigated from 0 to 3, during the third pass navigated from 0 to 2, during the fourth pass navigated from 0 to 1 and during the fifth pass navigated from 0 to 0.

Hence the navigation loop can be controlled using the outer loop

for(j=n-2;j>=0;j--)

Putting all together:

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

Program:

#include<stdio.h>
int main()
{
int a[50],n,i,j,temp;
/* accepting elements into array*/
printf("How many elements?");
scanf("%d",&n);
printf("Enter %d elements:\n",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
/* sorting the elements */
for(j=n-2;j>=0;j--)
  for(i=0;i<=j;i++)
    if(a[i+1]<a[i])
    {
      temp=a[i];
      a[i]=a[i+1];
      a[i+1]=temp;
    }
/* printing the array elements */
printf("Elements in ascending order:\n");
for(i=0;i<n;i++)
   printf("%5d",a[i]);
return 0;
}

Execution:
How many elements?6
Enter 6 elements:
25  20  22  11  8  18
Elements in ascending order:
8   11   18   20   22   25

Sorting elements in descending order using bubble sort:

Program:

#include<stdio.h>
int main()
{
int a[50],n,i,j,temp;
/* accepting elements into array*/
printf("How many elements?");
scanf("%d",&n);
printf("Enter %d elements:\n",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
/* sorting the elements */
for(j=n-2;j>=0;j--)
  for(i=0;i<=j;i++)
    if(a[i+1]>a[i])
    {
       temp=a[i];
       a[i]=a[i+1];
       a[i+1]=temp;
    }
/* printing the array elements */
printf("Elements in descending order:\n");
for(i=0;i<n;i++)
   printf("%5d",a[i]);
return 0;
}

Execution:
How many elements?6
Enter 6 elements:
25  20  22  11  8  18
Elements in ascending order:
25   22   20   18   11    8

Previous post:

Next post: