17 views

Question – In the best case, what is the minimum number of swaps are possible using Selection Sort Algorithm?

My Take – Best case –> means can we take input array as best case is mentioned – like already sorted Array (ascending or reverse sorted) array in both cases Selection Sort makes zero swaps i.e Ɵ(1)

But I remember Arjun Sir once mentioned that – Best case for worst case Input. So, should we take unsorted array and like 213 and say minimum number of swaps selection sort can make is Ɵ(n)

| 17 views
0
What do you "want" to mean by best case for worst case input? Cases are obviously for inputs afaik.
+1
When the array is sorted, the number of swaps→ O(1)

When unsorted → O(n)
+1
No matter whether the array is sorted or not but selection sort has to compare the element $e_i$ with all the elements of the array. So this comparison goes as like

= (n-1) comparision for $1^{st}$ element + (n-2) comparison for $2^{nd}$ element + $\dots + 2+1$

= $O(n^2)$

but number of swap will vary, as in best case it will be $O(1)$ but in worst case it will be $O(n)$ and when we find the complexity of sort so we have to consider both $\text{number of comparision + number of swaps}$