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 Show 14 previous comments 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.