October 15, 2023
October 15, 2023
October 15, 2023
###### GATE 2009
October 15, 2023
 Question 11

What is the number of swaps required to sort n elements using selection sort, in the worst case?

 A θ(n) B θ(n log n) C θ(n2) D θ(n2 logn)
Question 11 Explanation:
Selection sort – There is no Worst case input for selection sort. Since it searches for the index of kth minimum element in kth iteration and then in one swap, it places that element into its correct position. For n-1 iterations of selection sort, it can have O(n) swaps. Selection Sort does a significant number of comparisons before moving each element directly to its final intended position. At most the algorithm requires N swaps. once we swap an element into place, you never go back again.So it is great for writes O(n) but not so great (at all) for reads — O(n2). It isn’t well-suited to generalized sorting, but might work well in specialized situations like EEPROM (where writes are inordinately expensive).
Question 11 Explanation:
Selection sort – There is no Worst case input for selection sort. Since it searches for the index of kth minimum element in kth iteration and then in one swap, it places that element into its correct position. For n-1 iterations of selection sort, it can have O(n) swaps. Selection Sort does a significant number of comparisons before moving each element directly to its final intended position. At most the algorithm requires N swaps. once we swap an element into place, you never go back again.So it is great for writes O(n) but not so great (at all) for reads — O(n2). It isn’t well-suited to generalized sorting, but might work well in specialized situations like EEPROM (where writes are inordinately expensive).