For my Data Structure Students - Bubble Sort...

As a professor of computer science i have started recapitulating the basic theoretical computer science. Few days back i have written the code for bubble sort and did its analysis. I would like to share it with the student community...

You can find the source code from here.

The result of the above program is shown below.

Please have a look at how at each pass of the outer loop the large numbers are pushed towards the end.


Analysis:

The outer loop of the bubblesort algorithm does n times. For first outer loop the inner loop is for n-1 times, for second outer loop the inner loop is for n-2 times and so on.

Hence total loop count is (n-1) + (n-2) +........+2+1 = n*(n-1)/2

Hence O(n) = n^2

Hope this discussion helps the student community...