bubblesort(A, n) for i from 1 to n − 1 for j from n to i + 1 if A[j] < A[j − 1] swap(A[j], A[j − 1]) (a) What is the loop invariant for bubblesort? (b) State briefly a proof of correctness. (c) Derive concisely the worst-case running time of bubblesort as a function of the input array size n? Show your work! (d) Derive concisely the best-case running time as a function of n. Show your work!
Subject - Design & Anal
Please complete all the questions together.
Thank you in Advance.
Consider the following pseudocode for bubblesort:
bubblesort(A, n)
for i from 1 to n − 1
for j from n to i + 1
if A[j] < A[j − 1]
swap(A[j], A[j − 1])
(a) What is the loop invariant for bubblesort?
(b) State briefly a proof of correctness.
(c) Derive concisely the worst-case running time of bubblesort as a function of the input array size
n? Show your work!
(d) Derive concisely the best-case running time as a function of n. Show your work!
Answer:
(a) The loop invariant for bubblesort is that after each iteration of the outer loop (from i=1 to n-1), the subarray A[1:i-1] is sorted in non-descending order.
(b) A proof of correctness for bubblesort can be given using loop invariants. To prove that bubblesort correctly sorts an array of n elements, we need to show that the loop invariant is true before the first iteration of the outer loop, is maintained through each iteration of the outer loop, and guarantees correctness at termination.
Step by step
Solved in 3 steps
