Question 4: [30 points] Let A[1..n] be an array of n distinct numbers Consider s

Question

Question 4: [30 points] Let A[1..n] be an array of n distinct numbers Consider sorting n numbers stored in array A, by first finding the smallest element of A and exchanging it with the element in A[1]. Then find the second smallest element of A, and exchange it with A[2]. Continue like this for the first n-1 elements of A. Write pseudocode for this algorithm, which is known as Selection Sort. Use the CLRS syntax or something closer to that for your pseudocode (similar to homework 1) a) b) Why does it need to run for only the first n-1 elements rather than for all n elements? c) Give the best and worst case running time of selection sort in -notation.

Explanation / Answer

3) For j=i+1 to n

(b) It runs for first n-1 elements only because the last element is already sorted as the only element left is the largest in the array beacuse we are picking smaller numbers in every iteration.

(c) Selecting the lowest element requires scanning all n elements (this takes n 1 comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining n 1 elements and so on, for (n 1) + (n 2) + ... + 2 + 1 = n(n - 1) / 2 (n2) comparisons. Each of these scans requires one swap for n 1 elements (the final element is already in place).

So, Time Complexity = (n2) in both the best case and worst case as the number of swaps are always (n2)

In best case no swaps are there.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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