Bubble Sort
Table of Content
- Introduction
- Basic Idea
- Algorithm
- Program in C language
- 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
- #include<stdio.h>
- #include<conio.h>
- void Bubblesort(int A[],int n);
- void printlist(int A[],int n);
- void main()
- {
- int A[20],n;
- int i;
- printf("\nEnter the number of element\n");
- scanf("%d",&n);
- printf("\nNow enter the elements\n");
- for(i=0;i<n;i++)
- {
- scanf("%d",&A[i]);
- }
- printf("\nElement present in the array before sort\n");
- printlist(A,n);
- Bubblesort(A,n);
- printf("\nElement present in the array after sort\n");
- printlist(A,n);
- getch();
- }
- void Bubblesort(int A[],int n)
- {
- int i,j,temp;
- for(i=0;i<n;i++)
- {
- for(j=1;j<n-i;j++)
- {
- if(A[j-1]>A[j])
- {
- temp=A[j-1];
- A[j-1]=A[j];
- A[j]=temp;
- }
- }
- }
- }
- void printlist(int A[],int n)
- {
- int i;
- for(i=0;i<n;i++)
- {
- printf("%d",A[i]);
- }
- }
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
