30 votes 30 votes What is the number of swaps required to sort $n$ elements using selection sort, in the worst case? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n^2)$ $\Theta(n^2 \log n)$ Algorithms gatecse-2009 algorithms sorting easy + – Kathleen asked Sep 22, 2014 edited Oct 24, 2016 by go_editor Kathleen 27.6k views answer comment Share Follow See 1 comment See all 1 1 comment reply PiratedVirus commented Dec 17, 2018 reply Follow Share Selection sort: 2 votes 2 votes Please log in or register to add a comment.
Best answer 31 votes 31 votes The answer is A. In worst case, we have $1$ swap in each loop except the last one and hence $n-1$ swaps at max for $1$ to $n$. Therefore the worst case number of swaps is $\Theta(n)$ Gate Keeda answered Dec 10, 2014 edited Dec 19, 2022 by Abhrajyoti00 Gate Keeda comment Share Follow See all 3 Comments See all 3 3 Comments reply reena_kandari commented Nov 28, 2017 reply Follow Share 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$ 18 votes 18 votes Queenia Agrawal commented Jan 20, 2018 reply Follow Share @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 1 votes 1 votes Manu Shaurya commented Jun 6, 2019 reply Follow Share A minor correction, in worst case , selection sort does n-1 swaps. 0 votes 0 votes Please log in or register to add a comment.
4 votes 4 votes option a abhishekmehta4u answered Mar 23, 2019 abhishekmehta4u comment Share Follow See 1 comment See all 1 1 comment reply ashutoshkpandey commented Oct 11, 2021 reply Follow Share Nice I confused in n2 and n. Now my confusion is clear thanks. 0 votes 0 votes Please log in or register to add a comment.