Question

2.2-2 Consider sorting numbers stored in array by first finding the smallest element n A of and exchanging it with the element in . Then find the second smallest A AOE1 element of A, and exchange it with . Continue in this manner for the firs AOE2 1 elements of A. Write pseudocode for this algorithm, which is known as selection sort. What loop invariant does this algorithm maintain? Why does it need to run for only the firs elements, rather than for all elements? Give the best-case n 1 n and worst-case running times of selection sort in ‚-notation.

Answer 1

Answer:

Follows are the explanation of the choices:

Explanation:

Following are the Pseudocode for selection sort:                      

for j = 0 to k-1 do:

      SS = i

      For l = i + 1 to k-1 do:

        If X(l) < X(SS)

          SS= l

        End-If

      End-For

      T = X(j)

      X(j) = X(SS)

      X(SS) = T

    End-For

Following are the description of Loop invariants:

The subarray  A[1..j−1] includes the lowest of the j−1 components, ordered into a non-decreasing order, only at beginning of the iteration of its outer for loop.  

A[min] is the least amount in subarray A[j.. l−1] only at beginning of the each loop-inner iterations.                      

Following are the explanation for third question:

Throughout the final step, two elements were left to evaluate their algorithm. Its smaller in A[k-1] would be placed as well as the larger in A[k]. One last is the large and medium component of its sequence because most and the last two components an outer loop invariant has been filtered by the previous version. When we do this n times, its end is a repetitive, one element-sorting phase.

Following is the description of choosing best-case and worst-case in run- time:

The body the if has never been activated whenever the best case time is the list is resolved. This number of transactions are especially in comparison also as a procedure, that will be (n-1)(((n+2)/2)+4).    

A structure iterator at every point in the worst case that array is reversed, that doubles its sequence of iterations in the inner loop, that is:(n−1)(n+6) Since both of them take timeΘ(n2).