1.6k 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}$)
edited | 1.6k views
0
this question is asked 3 times in gate 2006 , 2009 , and  2013

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

0
https://www.geeksforgeeks.org/selection-sort/

1
2