Analysis of Bubble Sort :

Here is the observable :

Analysis of Bubble Sort !

For understanding the algorithm of bubble sort .
click the link below :
Bubble sort

In several ways we can modify our algorithm , this first is :

1. Clearly the sorting is done by bubbling the greatest unsorted element to a higher indices each time . So , this makes a two different parts of the array .

1. Sorted 
2. Unsorted 

If we put a loop to print the array[] , after each pass , we will clearly understand how the list is divided in two parts . 1. sorted 2. unsorted .

So, What if we exclude the the sorted portion in our algorithm . For sure this will reduce the number of loops and hence time !

As with every loop elements are getting sorted from the end , We can decrease the running of inner loop with every pass . 

This can be done by replacing condition

j<n-1 with j<n-i-1 !

Eg.

This will reduce the compilation time and result is still as it was !

2. Another thing we can do is adding a variable - "flag".

Our intention is to terminate the loop if the list is sorted .

We can do this by checking , whether swapping is done or not . Like , if swapping is not done means the list is sorted , and we can terminate the loop .

So , for this ,

•  initialize a variable "flag = 0" , in outer for loop.
• Change value of flag to 1 , "flag = 1" in the Swapping block .
• and In outer for loop at the end give a conditional if statement such as , if flag=0 -> break;
• This will terminate the loop if no swapping is done, i.e. If list is already sorted !

Ex.

So , In this way Bubble sort  WAS so time consuming , we made it better than before !

Any suggestions and modifications are always accepted !

link to :
1.Bubble sort
2.Selection sort 

---

Thank you !