1 Find the best and worst case complexity of the Bubble Sort

1. Find the best and worst case complexity of the Bubble Sort algorithm for sorting n elements for each of the following operations: # of passes, # of exchanges and # of comparisons.

Bubble-Sort (A, n)

//Sorts the Array A(1:n) in non-decreasing order.

Last n - 1, limit n – 1, switch true // last represents last item switched

while switch = true do

    switch false                                      

    for j = 1 to limit do

        if A(j) > A(j _{+ 1}) then

            exchange (A(j), A(j + 1)) // t A(j), A(j) A(j + 1), A(j + 1) t   

                                   switch true

                                    last j

                                endif

                           endfor

                           limit = last -1

                       endwhile

Solution

The best case runtime for this algorithm is O(1). This case occurs when the given array is already sorted. The worst case run time of the algorithm is O(n^2). This case occurs when the given array is in descending order.