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.
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...