ISRO2008-77

Question

How many comparisons are needed to sort an array of length $5$ if a straight selection sort is used and array is already in the opposite order?

• A. $1$
• B. $10$
• C. $15$
• D. $20$

Answer 1

From Wikipedia 

Selection sort is not difficult to analyze compared to other sorting algorithms since none of the loops depend on the data in the array. Selecting the lowest element requires scanning all nelements (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 ∈ Θ(n^2) comparisons.

 

 So whatever order they are arranged the number of comparisons will be sum of n-1 terms. 

Here n=5

So total comparisons= 4*(4+1)/2=10.

 

 

Comments

what is the formula actually?...Is it n(n-1)/2 or n(n+1)/2?...Please reply ASAP.

---

dont follow the formula, follow the general algorithm

It will be easy.

It is n(n - 1)/2

---

N(N-1)/2

Answer 2

b) 10

---

each cell denote the total number of comparison performed to select the element to be placed in that cell.

4

3

2

1

0

Answer 3

The number of comparisons needed will be..

1st Iteration - 4

2nd Iteration - 3

3rd Iteration -2

4rth Iteration -1

So to fully sort - 4+3+2+1 = 10 comparisons are needed.