1. Find the best and worst case complexity of the Bubble Sort algorithm for sort
ID: 3793102 • Letter: 1
Question
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
Explanation / Answer
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.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.