The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
1.1k 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 (346k points)
edited by | 1.1k views

1 Answer

+22 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 Veteran (14.3k points)
edited by
(n-1) swaps to be precise
I should have written it with big oh notation
okay :)
Word swap is important!

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

The question asks only for the number of swaps.

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

Then you should never open that book again
ha ha ha :-D


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

33,687 questions
40,230 answers
114,268 comments
38,795 users