37 votes 37 votes Which one of the following is the tightest upper bound that represents the number of swaps required to sort $n$ numbers using selection sort? $O(\log n$) $O(n$) $O(n \log n$) $O(n^{2}$) Algorithms gatecse-2013 algorithms sorting easy + – Arjun asked Sep 23, 2014 • edited Nov 14, 2017 by kenzou Arjun 10.1k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply register_user_19 commented Dec 5, 2018 reply Follow Share this question is asked 3 times in gate 2006 , 2009 , and 2013 9 votes 9 votes paraskk commented Jun 15, 2019 reply Follow Share What a tricky question!! Blink and miss ! 2 votes 2 votes svas7246 commented Mar 4, 2021 reply Follow Share An example where we can find n-1 swaps 23,78,45,8,32,46 0 votes 0 votes palashbehra5 commented Aug 12, 2021 reply Follow Share @paraskk TBH most of the gate questions are like that only :P 0 votes 0 votes Please log in or register to add a comment.
Best answer 40 votes 40 votes 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)$ Correct Answer: $B$ Bhagirathi answered Sep 23, 2014 • edited Apr 29, 2019 by Naveen Kumar 3 Bhagirathi comment Share Follow See all 17 Comments See all 17 17 Comments reply Arjun commented Sep 23, 2014 reply Follow Share (n-1) swaps to be precise 47 votes 47 votes Bhagirathi commented Sep 23, 2014 reply Follow Share I should have written it with big oh notation 1 votes 1 votes Arjun commented Sep 24, 2014 reply Follow Share okay :) 1 votes 1 votes tocshark commented Feb 1, 2017 reply Follow Share Word swap is important! 1 votes 1 votes anchitjindal07 commented Sep 23, 2017 reply Follow Share But the time complexity of Selection Sort is O(n2).. There are two loops, one inside the other 0 votes 0 votes Arjun commented Sep 23, 2017 reply Follow Share The question asks only for the number of swaps. 1 votes 1 votes anchitjindal07 commented Sep 23, 2017 reply Follow Share 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). 0 votes 0 votes Arjun commented Sep 23, 2017 reply Follow Share Then you should never open that book again 32 votes 32 votes Sunny Mukherjee commented Jan 30, 2018 reply Follow Share ha ha ha :-D 0 votes 0 votes Ayush Upadhyaya commented Jan 6, 2019 reply Follow Share 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 } 2 votes 2 votes Nandkishor3939 commented Jan 6, 2019 reply Follow Share @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 votes 0 votes Gurdeep Saini commented Jan 12, 2019 i edited by Gurdeep Saini Jan 12, 2019 reply Follow Share @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 votes 0 votes Ayush Upadhyaya commented Jan 12, 2019 reply Follow Share @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 votes 0 votes Gurdeep Saini commented Jan 12, 2019 reply Follow Share https://www.geeksforgeeks.org/selection-sort/ 0 votes 0 votes Anju Mehral commented Jan 5, 2020 i reshown by Anju Mehral Jan 5, 2020 reply Follow Share but tightest upper bound means best case and in best case we'll take sorted array then in that case there would be no requirement for swapping .....we'll simply traverse entire array which would take o(n) time ......correct me if I'm wrong :) 0 votes 0 votes Mayank0343 commented Jan 28, 2020 reply Follow Share will the maximum number not be n/2. If we have made n/2 swaps .. that would mean the rest half of the elements would already be in their right positions 0 votes 0 votes Gaurav nitkkriit commented Feb 1, 2021 reply Follow Share Number of swap in selection sort is always n-1 0 votes 0 votes Please log in or register to add a comment.
4 votes 4 votes Best, Average and worst case will take maximum O(n) swaps. Selection sort time complexity O(n2) in terms of number of comparisons. Each of these scans requires one swap for n-1 elements (the final element is already in place). varunrajarathnam answered Sep 24, 2020 varunrajarathnam comment Share Follow See all 0 reply Please log in or register to add a comment.