BubbleSort_analysis

Analysis OF Bubble Sort : Analysis OF Bubble Sort Analysis of ‘Bubble sort’ is very simple. There are (n-1) passes. In the first pass there are (n-1) comparison, in second pass there are (n-2) comparison, in third pass (n-3) comparison and so on. Thus Total number of comparison = (n-1) + (n-2) + (n-3) + … + 3 + 2+1 = (n*(n-1))/2 Hence the sort function f(n) = (n*(n-1))/2 = (n?2 – n)/2 = O(n?2) The number of interchanges depend on the original file or array but it cannot be greater than the number of comparison. In the best case, when the array / file is already sorted or almost sorted, we can only reduce the number of passes. In case a file is sorted no interchanges are made on any pass. Hence the number of passes can be reduced by keeping a record of whether or not any interchanges are made on any pass. Modification : In order to reduce number of passes a check counter could be used which would return a true value ( 1 ) whenever exchange or swapping of elements take place, otherwise it would return the value false ( 0 ). If the value of the check counter remains zero ( 0) after one complete iteration of the inner loop ( j loop), then it can be concluded that no exchange of elements have taken place, that is, the array has been sorted. This can be achieved by adding few statements.