02) (20 pts) Consider sorting n numbers stored in array A by first finding the s

Question

02) (20 pts) Consider sorting n numbers stored in array A by first finding the smallest element of A ane exchanging it with the element in AlIJ. Then find the second smallest element of A. and exchange it with Al2]. Continue in this manner for the first n-1 elements of A. a) (10 pts) Write pseudocode for this algorithm, which is known as selection sort b) (5 pts) What loop invariant does this algorithm maintain? Why does it need to run for only the first n- 1 elements, rather than for all n elements? e) (5 pts) Calculate the best-case and worst-case running times of selection sort in e- notation

Explanation / Answer

Ans A).

Selection Sort Algorithm:

Ans B).

Consider this example where there are five elements in the array.

Although it has five elements but still the sorting algorithm runs for only 4 steps this indicates that it run for only n-1 elements, rather than n elements. This happens because after n-1 steps the last element get sorted automatically i.e, it is the last smallest element that remains for sorting so there is no other element left other than the last one to be compared and to put it at the correct index.

Ans C).

To find the minimum element from the array of N elements, N1 comparisons are required. After putting the minimum element in its proper position, the size of an unsorted array reduces to N1 and then N2comparisons are required to find the minimum in the unsorted array.

Therefore (N1) + (N2) + .............. + 1 = (N(N1))/2 comparisons and N swaps result in the overall complexity of

Theta(N2) for both Worst Case and Best Case running time.

Related Questions

Navigate

• Browse (All)
• Browse
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.