1.6k views

What is the number of swaps required to sort $n$ elements using selection sort, in the worst case?

1. $\Theta(n)$

2. $\Theta(n \log n)$

3. $\Theta(n^2)$

4. $\Theta(n^2 \log n)$

edited | 1.6k views
0

Selection sort:

The answer is A.

we have $1$ swap in each loop and hence $n$ swaps at max for $1$ to $n$. Therefore the worst case number of swaps is $\Theta(n)$

answered by Boss (19.9k points)
edited by
+8
Best case: $0$ swaps. for eg $1,2,3,4,5,6$

Worst case: $n-1$ swaps for eg $6,5,2,1,4,3$
+1

@reena ma'am, it depends on implementation, but in its basic form, even in best case selection sort requires 1 swap in each pass. https://stackoverflow.com/questions/26688765/what-are-the-number-of-swaps-required-in-selection-sort-for-each-case

0
A minor correction, in worst case , selection sort does n-1 swaps.
+1 vote

option a

answered by Boss (33.9k points)

1