###### UGC NET CS 2016 July- paper-2

October 15, 2023###### GATE 2009

October 15, 2023# GATE 2009

Question 11 |

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

θ(n) | |

θ(n log n) | |

θ(n ^{2}) | |

θ(n ^{2} logn) |

Question 11 Explanation:

Selection sort – There is no Worst case input for selection sort. Since it searches for the index of k

^{th}minimum element in k^{th}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(n^{2}). It isn’t well-suited to generalized sorting, but might work well in specialized situations like EEPROM (where writes are inordinately expensive).Correct Answer: A

Question 11 Explanation:

Selection sort – There is no Worst case input for selection sort. Since it searches for the index of k

^{th}minimum element in k^{th}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(n^{2}). It isn’t well-suited to generalized sorting, but might work well in specialized situations like EEPROM (where writes are inordinately expensive). Subscribe

Login

0 Comments