Answer to Question #260072 in Algorithms for anju

Question

Write bubble sort algorithm and analysis it for best case and worst case time complexity using tabular method. Represent the time complexity using Theta(Ө) notation.

Answer 1

Bubble short algorithm-

start
arr[]
temp
 for(i=0;i<n-1;i++)
    for(j=0;j<n-i-1;j++)
      if(arr[j]>arr[j-1])
        temp=arr[j-1]
        arr[j-1]=arr[j]
        arr[j]=temp

Time complexity -

Best case analysis:

When array is already sorted but for loop will still check. So complexity is O(n)

Worst Case Analysis:

When array is not sorted, in that case two for loop will be initiated and run so complexity $O(n^2)$

Average case analysis:

It comprises O(n/2) passes, and O(n) comparison for each pass.

Hence, average case time complexity for the bubble sort $\theta (n^2)$

Space complexity -

It uses constant amount of space, hence the space complexity of the bubble sort is O(1).