The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
1.4k views

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

  1. $O(\log n$)
  2. $O(n$)
  3. $O(n \log n$)
  4. $O(n^{2}$)
asked in Algorithms by Veteran (363k points)
edited by | 1.4k views

1 Answer

+23 votes
Best answer
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)$
answered by Boss (14.4k points)
edited by
+22
(n-1) swaps to be precise
+1
I should have written it with big oh notation
0
okay :)
+1
Word swap is important!
0

But the time complexity of Selection Sort is O(n2).. There are two loops, one inside the other

0
The question asks only for the number of swaps.
0

Ok. Thanks Sir... The book from where I read has given wrong algorithm, saying it to be Selection Sort.. As per that algorithm, number of swaps are also O(n2).

+10
Then you should never open that book again
0
ha ha ha :-D
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,568 questions
48,554 answers
155,365 comments
63,554 users