The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
1.7k 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 (396k points)
edited by | 1.7k views
0
this question is asked 3 times in gate 2006 , 2009 , and  2013

1 Answer

+24 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.5k points)
edited by
+27
(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).

+11
Then you should never open that book again
0
ha ha ha :-D
0
for(i=0;i<n-1;i++)
{
    min_idx=i;
    for(j=i+i;j<n;j++)
    {
        if(a[j]<a[min_idx])
        min_idx=j;
    }
    swap(a[i],a[min_idx]); // only 1 swap each iteration for a total of n-1 iterations
}

 

0

@Ayush Upadhyaya  In this algorithm , the first loop should be

for(i=0;i<n-2;i++)

as  for the lase element we don't need any comparison.

0

@Ayush Upadhyaya typing mistake at j=i+1

edit i want  to say that it should be i+1 but typed as i+i

0

@Nandkishor3939-$i \lt n-1$ will ensure last value at which loop runs is $n-2$ only.

@Gurdeep Saini-Why j should not be $i+1$ ? :O

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
50,132 questions
53,252 answers
184,792 comments
70,509 users