Consider the sorting algorithm shown below -------------------------------------
ID: 669107 • Letter: C
Question
Consider the sorting algorithm shown below
--------------------------------------------------------------------------------------------------------------------------------------------------------
Algorithm: BUBBLESORT
Input: An array A[1...n] of n elements.
Output: A[1...n] sorted in nondecreasing order.
i <--- 1; sorted <--- false;
while i <= -1 and not sorted
sorted <--- true;
for j <--- n downto i+1
if A[j] < A[j-1] then
interchange A[j] and A[j-1]
sorted <--- false;
end if
end for
i <--- i + 1;
end while
--------------------------------------------------------------------------------------------------------------------------------------------------------
(a) What is the minimum number of element comparisons performed by the algorithm? When is this minimum achieved?
(b) What is the maximum number of element comparisons performed by the algorithm? When is this maximum achieved?
(c) What is the minimum number of element assignments performed by the algorithm? When is this minimum achieved?
(d) What is the maximum number of element assignments performed by the algorithm? When is this maximum achieved?
(e) Express the running time of Algorithm bubblesort in terms of the O and notations.
(f) Can the running time of the algorithm be expressed in terms of the -notation? Explain.
Explanation / Answer
Assumption: 'Element' means element of the array, as it is not mentioned in the question clearly.
1.
Minimum number of element comparisons performed by the algorithm = 0
When the array passed is already sorted.
2.
Maximum number of element comparisons performed by the algorithm = (n - 1) * (n) / 2
When the array passed is sorted in reverse order.
3.
Minimum number of element assignments performed by the algorithm = 0
When the array passed is already sorted, the control won't enter the if block, so no 'element' assignments.
4.
Maximum number of element assignments performed by the algorithm = 0
When the array passed is reverse sorted, the control will enter the if block in every loop, so n * (n - 1) 'element' assignments.
5.
Worst case Complexity:
O(n^2)
Omega(n^2)
6.
Yes, it can be written in theta notation:
theta(n^2)