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

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 (359k 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.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

41,146 questions
47,708 answers
62,405 users