Consider the following sort algorithm. Using asymptotic notations answer the fol
ID: 3835860 • Letter: C
Question
Consider the following sort algorithm. Using asymptotic notations answer the following (justify your answers): What are the minimum and maximum number of swap operations that could be performed in one run of the algorithm on an input array? What kind of input array results in the minimum number of swap operations? What kind of input array results in the maximum number of swap operations? What are the best case and worst case run times of the algorithm in terms of asymptotic notations? Explain. Do the best and worst case run times of this algorithm differ? Explain. void sort (A[1 ... n]) {//A is an array of length n n = length (A) for (i = 1 to n-1) {min i for (j = i + 1 to n) {if (A[j]Explanation / Answer
Firstly to specify, the give algorithm implements the selection sort.
Now coming to the questions.
i) What are the minimum and maximum number of swap operations that could be performed in one
run of the algorithm on an input array?
The swaps could never happen, if the list is readily sorted, i.e.,
when the condition if(min != i) never satisfies.
Therefore, the minimum number of swaps is 0.
The maximum number of swap operations could happen, when the same condition always happens,
i.e., when the list is in reverse sorted order, and in that case, the maximum number of
swaps are: the number of times the outer loop runs, i.e., for n-1 times.
ii)What kind of input array results in the minimum number of swap operations?
As explained in question 1, if the list is already sorted, no swaps will happen which
is the minimum number of swaps.
iii)What kind of input array results in the maximum number of swap operations?
As explained in question 1, if the list is reverse sorted, all swaps will happen which
is the maximum number of swaps.
iv)What are the best case and worst case run times of the algorithm in terms of asymptotic
notations? Explain.
With reference to the algorithm, all the comparisons are based on the index values.
And the basic operation in the algorithm is the comparison, and not the swap, and comparison
will happen equal number of times, and is independent of the input array values.
Therefore, either in the best case or worst case, the run times of the algorithm is:
O(n^2).
v) As explained in question iv) there will be no difference with best and worst case run times
for this algorithm.