GATE CSE 2013 | Question: 6

Question

Which one of the following is the tightest upper bound that represents the number of swaps required to sort $n$ numbers using selection sort?

• A. $O(\log n$)
• B. $O(n$)
• C. $O(n \log n$)
• D. $O(n^{2}$)

Comments

this question is asked 3 times in gate 2006 , 2009 , and  2013

---

What a tricky question!! Blink and miss !

---

An example where we can find n-1 swaps

23,78,45,8,32,46

---

@paraskk TBH most of the gate questions are like that only :P

Answer 1

In selection max you can do is $n$ swaps..selecting the smallest element from all the elements and replacing it correct position so $O(n)$

Correct Answer: $B$

Comments

but tightest upper bound means best case and in best case we'll take sorted array then in that case there would be no requirement for swapping .....we'll simply traverse entire array which would take o(n) time ......correct me if I'm wrong :)

---

will the maximum number not be n/2.  If we have made n/2 swaps .. that would mean the rest half of the elements would already be in their right positions

---

Number of swap  in selection sort is always n-1

Answer 2

Best, Average and worst case will take maximum O(n) swaps.
Selection sort time complexity O(n2) in terms of number of comparisons. Each of these scans requires one swap for n-1 elements (the final element is already in place).