Sorting Technique | Bubble Sort | Data Structure Lecture Series

 

Bubble Sort

Table of Content

1. Introduction
2. Basic Idea
3. Algorithm
4. Program in C language
5. Analysis of this algorithm
   
   

1. Introduction 

Sorting is the problem of arranging element in either increase order or decreasing order. Bubble Sort is one of the Sorting technique that solve this problem by comparing the elements of Array.

2. Basic Idea 

Basic idea Behind, this Sorting technique is place the largest element to its correct position by comparing its with neighbors. similarly second largest element and so on pass by pass.

 3. Algorithm 

Input: A unsorted array A[ ] of size N & 

output: A sorted array A[ ] of size N

------------------------------------------------------------------------------------------------------------------- 

Step 1: Set I equal to 0

Step 2: Repeat Step 3 to Step 4 until I less than N 

Step 3: Set J equal to 0

Step 4: Repeat Step 5 until J less than N-I-1 

Step 5: if A[J]>A[J+1] than go for Step 6 otherwise move to next

Step 6:  Swap (A[j],A[j+1]) 

Step 7: Print the Element of Sorted Array 

--------------------------------------------------------------------------------------------------------------------

4. Program in C language

1. #include<stdio.h>
2. #include<conio.h>
3. void Bubblesort(int A[],int n);
4. void printlist(int A[],int n);
5. void main()
6. {
7.  int A[20],n;
8.  int i;
9.  printf("\nEnter the number of element\n");
10.  scanf("%d",&n);
11.  printf("\nNow enter the elements\n");
12.  for(i=0;i<n;i++)
13.  {
14.    scanf("%d",&A[i]);
15.  }
16.  printf("\nElement present in the array before sort\n");
17.  printlist(A,n);
18.  Bubblesort(A,n);
19.  printf("\nElement present in the array after sort\n");
20.  printlist(A,n);
21.  getch();
22. }
23. void Bubblesort(int A[],int n)
24. {
25. int i,j,temp;
26. for(i=0;i<n;i++)
27. {
28.      for(j=1;j<n-i;j++)
29.      {
30.           if(A[j-1]>A[j])
31.           {
32.                temp=A[j-1];
33.                A[j-1]=A[j];
34.                A[j]=temp;
35.           }
36.      }
37. }
38. }
39. void printlist(int A[],int n)
40. {
41. int i;
42. for(i=0;i<n;i++)
43. {
44.   printf("%d",A[i]);
45. }
46. }

5. Analysis of this algorithm

let take one example 

  20, 6, 7, 5, 3 , 2 

Pass 1: when I = 0

20, 6 , 7, 5, 3, 2

Here First we compare 20 with 6 as it is bigger than 6 just simply swap it  

6, 20, 7 , 5, 3, 2

Here First we compare 20 with 7 as it is bigger than 7 just simply swap it   

6, 7, 20, 5 , 3, 2

Here First we compare 20 with 5 as it is bigger than 5 just simply swap it  

6, 7, 5, 20, 3 , 2

Here First we compare 20 with 3 as it is bigger than 3 just simply swap it 

6, 7, 5, 3, 20, 2 

Here First we compare 20 with 2 as it is bigger than 2 just simply swap it  

6, 7, 5, 3, 2, 20

Here is final array after pass 1 what we observe here Largest in array get placed in last position and second observation is that here we perform N-1 comparison mean 5 comparison.

Pass 2: when I = 1 

 6, 7, 5, 3, 2, 20

Here First we compare 6 with 7 as it is smaller than 7 just simply move to next step

6, 7 , 5 , 3, 2, 20

Here First we compare 7 with 5 as it is bigger than 7 just simply swap it   

6, 5, 7 , 3 , 2, 20

Here First we compare 7 with 3 as it is bigger than 3 just simply swap it    

6, 5, 3, 7 , 2 , 20

Here First we compare 7 with 2 as it is bigger than 2 just simply swap it     

6, 5, 3, 2, 7, 20

 Here is final array after pass 2 what we observe here second Largest in array get placed in second last position and second observation is that here we perform N-2 comparison mean 4 comparison.

similarly Pass are proceed and we reach to final position

what we observe here

In Pass 1: There are n-1 comparison

In Pass 2: There are n-2 comparison

.........................

In Pass n-2: There are 2 comparison

In Pass n-1: There are 1 comparison

In Pass n: There are 0 comparison

total number of comparison is 1 + 2 + 3 + 4+.....+n = n * (n-1)/2 Comparison

These are the number of comparison we have to perform in each case best, worst and average case so complexity of Bubble Sort is O(n^2)   

NOTE:

Make sure Bubble Sort is a Inplace and Stable Sorting Technique 

Share: