Register

GATE CSE 2009 | Question: 11

• edited by
27,981 views
30 votes
30 votes

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

  1. $\Theta(n)$

  2. $\Theta(n \log  n)$

  3. $\Theta(n^2)$

  4. $\Theta(n^2 \log  n)$

• edited by
User Avatar

2 Answers

Best answer
32 votes
32 votes

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)$

• edited by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

37 votes
37 votes
2 answers
1
Arjun asked Sep 23, 2014
10,175 views
GATE CSE 2013 | Question: 6
Which one of the following is the tightest upper bound that represents the number of swaps required to sort $n$ numbers using selection sort? $O(\log n$) $O(n$) $O(n \log n$) $O(n^{2}$)
Which one of the following is the tightest upper bound that represents the number of swaps required to sort $n$ numbers using selection sort?$O(\log n$)$O(n$)$O(n \log n$...
User Avatar
0 votes
0 votes
2 answers
3
naveen81 asked Jan 30, 2017
745 views
MadeEasy Subject Test: Algorithms - Sorting
a. i>0,K>0, a[K]> a[max] b. i>0,K<0, a[K]< a[max] c. i<0,K>0, a[K]> a[max] d. i>0,K>0, a[K]< a[max]
a. i>0,K>0, a[K] a[max]b. i>0,K<0, a[K]< a[max]c. i<0,K>0, a[K] a[max]d. i>0,K>0, a[K]< a[max]
User Avatar
7 votes
7 votes
3 answers
4
ajit asked Sep 20, 2015
9,848 views
ISRO2008-77
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? $1$ $10$ $15$ $20$
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?$1$$10$$15$$20$
User Avatar
Link Copied!