(Analyzing iterative algorithm) The following pseudocode sorts n numbers stored
ID: 3724287 • Letter: #
Question
(Analyzing iterative algorithm) The following pseudocode sorts n numbers stored in array A in an ascending order. This algorithm is called short bubble sort. Note that the index of the first element of array A is assumed to be 1 as in the textbook, not 0.
Short-Bubble-Sort( A, n )
current = 2;
done = false;
wh ile ((current <= n) and (not done))
done = true;
for index = n downto current //for (index = n; index >= current; index--)
if (values[index] < values[index-1])
Swap(values[index], values[index-1 ]);
done = false;
current++;
(1)Give the best-case running times of short bubble sort in E > -notation and justify your answer.
(2)Give the worst-case running times of short bubble sort in E> - notation and justify your answer.
(3)What(while)loop invariant does this algorithm maintain?
Explanation / Answer
(1)Give the best-case running times of short bubble sort in E > -notation and justify your answer.
Best case complexity is of order n. This takes place when the array is sorted and no swap() function is called (i.e. the done flag remains true). When the array is already sorted, the algorithm scans the content of the array only once and then terminates.
(2)Give the worst-case running times of short bubble sort in E> - notation and justify your answer.
Worst case complexity is of order n square (n^2). This takes place when in every pass at least one element is swapped and done remains false through out.
In the 1st pass inner loop iterate for n-1 time, in 2nd pass it iterates for n-2 times and so on. We know that if we sum them up (1 + 2 + … + n-1 = O(n^2)) the result is of order n^2
(3)What(while)loop invariant does this algorithm maintain?
We can clearly see the presence of two loop invariant.
I. Done: it indicates that none of the elements in the loop is swapped and hence all the elements are in order.
II. current: it indicates that how many elements in the array are already sorted. Once current is more than n, it indicates that all the elements in the loop are sorted and the outer loop terminates
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.