GATE CSE 2009 | Question: 11

Question

What is the number of swaps required to sort $n$ elements using selection sort, in the worst case?

• A. $\Theta(n)$

• B. $\Theta(n \log  n)$

• C. $\Theta(n^2)$

• D. $\Theta(n^2 \log  n)$

Comments

Selection sort:

 

Answer 1

The answer is A.

In worst case, we have $1$ swap in each loop except the last one and hence $n-1$ swaps at max for $1$ to $n$. Therefore the worst case number of swaps is $\Theta(n)$

Comments

Best case: $0$ swaps. for eg $1,2,3,4,5,6$

Worst case: $n-1$ swaps for eg $6,5,2,1,4,3$

---

@reena ma'am, it depends on implementation, but in its basic form, even in best case selection sort requires 1 swap in each pass. https://stackoverflow.com/questions/26688765/what-are-the-number-of-swaps-required-in-selection-sort-for-each-case

---

A minor correction, in worst case , selection sort does n-1 swaps.

Answer 2

option a

Comments

Nice I confused in n2 and n. Now my confusion is clear thanks.