Bubble Sort
In these section we will going to learn about Bubble sort in most simple and in more efficient way. So,lets dive into it.
Bubble sort:- In Bubble Sort we starts comparison from very first element. In bubble sort we arrange the elements in ascending order.
Let’s understand it with the help of an example-
10 6 12 18 9 1
First we compare 10 and 6 if 10 is greater than 6 we swap the 10 and 6 and so on. So, after First pass of bubble sort our array become like (6 10 12 9 1 18). After the first pass of bubble sort our largest element of array is at it sorted position or on its final position.
If there are n elements in First pass we require (n-1) comparisons. Like in our, example there are six elements so, in First pass we require 5 comparisons.
So, our array of Example is- 10 6 12 18 9 1
First Pass- 6 10 12 9 1 18 (n-1 Comaprison)
Second Pass- 6 10 9 1 12 18 (n-2 Comaprison)
Third Pass- 6 9 1 10 12 18 (n-3 Comaprison)
Fourth Pass- 6 1 9 12 18 (n-4 Comaprison)
Fifth Pass- 1 6 9 10 12 18 (1 Comaprison)
How many pass in Bubble sort:- If there are “n” elements we require (n-1) Passes.
How many Comparisons Performed by Bubble sort:-
1+2+3+ — — — — — — -+(n-3)+(n-2)+(n-1) =n(n-1/2)
Sum of first natural no=(n-1)(n-1+1)/2
=n(n-1)/2
=n²-n/2
=o(n²)
No of Comparison by Bubble Sort is the Time Complexity of Bubble Sort.
In Bubble sort Complexity is Defined in terms of Comparisons not in terms of Swap.
SWAP In Bubble Sort:-
Minimum no of swap = Zero (If Array is already Sorted)
Maximum no of swap = n(n-1)/2 (Per Comparison a swap)
Maximum no of swap is required is when our array is sorted in “Descending Order”/“Reverse Order”.
Now, we have basic understanding of Bubble sort now let’s dive into code of bubble sort so, we get an idea about how to implement bubble sort and how can we use it.
Code of Bubble Sort:-
Consider a array:- 60 17 65 15
if(a[i]>a[i+1])
{
swap(a[i],a[i+1])
}
Basic Algorithm For Understanding Bubble sort.
First Loop Decides no of passes and second loop to Decide no of comparsion.
Void Sort(int a[], int n) {
for(j=0;j<=n-2;j++)
{
for(i=0;i<n-1-j;i++)
{
if(a[i]>a[i+1)
{
c=a[i];
a[i]=a[i+1];
a[i+1]=c;
}
}
}
}
Can we Modify Bubble Sort:-
Yes, we can modify the Bubble Sort if in some pass there is no comparison we can say array is already sorted.
Minimum no of comparison = (n-1) [When array is already sorted]
Maximum no of comparison = n(n-1)/2 [When array is Reverse Sorted].