Question

It is common practice for banks to record account transactions in the chronological order that they were made. However, it is also common for people to prefer to order their transactions by check number, versus chronological order. This is essentially a problem of sorting a list initially ordered chronologically into one sorted by check number, where it is highly likely that the chronologically ordered list is almost already sorted by check number. Consider the following sorting algorithm where A is the already chronologically sorted list of transactions: for i = 2 to length (A) do v = A[i] j = i - 1 while j > 0 and A[j]. checknumber > v.checknumber do A[j + 1] = A[j] j = j - 1 end while A[j + 1] = v end for Using a loop invariant prove that the sorting algorithm is correct. What is the worst-case? Briefly explain. What is a tight bound for the worst-case runtime? What is the best-case? Briefly explain. What is a tight bound for the best-case runtime? Recall the MERGESORT algorithm discussed in lecture. Explain, between MERGE-SORT and the above sorting algorithm, which you would recommend to perform the reordering from chronological to check number?

Answer 1

(a)
1st iteration(for loop)--

i=2,j=1 , there will only be 1 while loop iteration and if the A[j].checknumber>A[i].checknumber they will be swapped

so now , first 2 elements of array are sorted

2nd iteration(for loop)--

i=3,j=2, now if A[i].checknumber>A[j].checknumber we dont need to check further as the first two elements are already sorted
       and if A[j].checknumber>A[i].checknumber then the algorithm will find the correct place for A[i] and place it there.
       so the array till i will become sorted.

Kth iteration(foor loop)--

i=k,j=k-1, now array till index k-1 is already sorted.
       So if A[k].checknumber>A[k-1].checknumber then the array is already sorted.
       If A[k].checknumber<A[k-1].checknumber then we need to find the correct place for A[k] and place it there.

Last iteration(for loop)--
Let length of array=l
i=l,j=l-1, now array till index l-1 is already sorted.
       So if A[l].checknumber>A[l-1].checknumber then the array is already sorted.
       If A[l].checknumber<A[l-1].checknumber then we need to find the correct place for A[l] and place it there.

       And hence the whole array will become sorted.

(b)
Worst case is when the array is sorted in decreasing order checknumber wise.
In every iteration we need to traverse all the way back to the first element.
Time complexity in worst case -- O(n²)

(c)
Tight bound for the worst case runtime O(n²)

(d)
Best case is when the array is already sorted in increasing order checknumber wise.
We just need n comparisions in that case.
We will never enter inside the inner while loop.
Time complexity in best case -- O(n)

(e)
Tight bound for the best case runtime is O(n)

(f)

As it is given in the question that chronologically ordered list is almost already sorted by check number so Merge sort take O(nlogn) time in best case but the given algorithm which is Insertion sort takes O(n) time in best case.So I would recommend using Insertion sort in this particular problem.