Tuesday 29 July 2014

Bubble Sorting

The word sorting means arranging items(elements of an array) in a pattern , basically ascending ,descending or alphabetically.
In Bubble sorting algorithm , consecutive adjacent pairs of elements in an array are compared with each other. Now, if we want to sort in an ascending order , we check if the element in the lower index is greater than the element of the higher index. If yes,then the elements are  interchanged,so that the smaller element is placed before the bigger one. If know then we iterate for the the next consecutive pair .

Java source code :


The output :


















Complexity : 
Please note that the complexity of any sorting algorithm depends on the number of comparisons made.
By comparisons, here i am referring to the if check condition on line 23 .

for i=0 ; number of comparisons in j = n-1
for i=1 ; number of comparisons in j = n-2
for i=2 ; number of comparisons in j = n-3
for i=3 ; number of comparisons in j = n-4
for i=4 ; number of comparisons in j = n-5
-----
-----
for i=n-1 ; number of comparisons in j = 0
-------------------------------------------
therefore : total number of comparisons = 0+1+2+....+(n-1)
                                                            =n(n-1)/2
                                                            =O(n^2) //quadratic complexity



No comments:

Post a Comment