edited by
27,567 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

2 Answers

Best answer
31 votes
31 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
Answer:

Related questions

48 votes
48 votes
5 answers
1
Kathleen asked Sep 22, 2014
21,127 views
In quick-sort, for sorting $n$ elements, the $\left(n/4\right)^{th}$ smallest element is selected as pivot using an $O(n)$ time algorithm. What is the worst case time com...
23 votes
23 votes
3 answers
2
Kathleen asked Sep 22, 2014
13,639 views
Consider a binary max-heap implemented using an array.Which one of the following array represents a binary max-heap?$\left\{25,12,16,13,10,8,14\right\}$ $\left\{25,14,...
46 votes
46 votes
7 answers
4
Kathleen asked Sep 22, 2014
20,942 views
The above DFA accepts the set of all strings over $\{0,1\}$ that begin either with $0$ or $1$.end with $0$.end with $00$.contain the substring $00$.