Awesome q2a theme
0 votes
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)

Please help, I’m kinda confused.

in Algorithms by (65 points) | 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}$

Please log in or register to answer this question.

Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Oct 2019
  1. GAITONDE

    410 Points

  2. Satbir

    317 Points

  3. Rudr Pawan

    163 Points

  4. srestha

    136 Points

  5. Mk Utkarsh

    127 Points

  6. Debapaul

    94 Points

  7. chandrikabhuyan8

    83 Points

  8. Shaik Masthan

    79 Points

  9. Verma Ashish

    77 Points

  10. !KARAN

    74 Points

Monthly Top User and those within 60% of his/her points will get a share of monthly revenue of GO subject to a minimum payout of Rs. 500. Current monthly budget for Top Users is Rs. 450.
1,680 questions
1,089 answers
4,559 comments
89,591 users