Question

Which are true of Selection Sort? please explain

Multiple answers:You can select more than one option

A) It uses Θ(n^2) comparisons in the worst case

B) It uses Θ(n^2) comparisons in the average case

C) It uses Θ(n^2) comparisons in the best case

D) It uses Θ(n^2) swaps in the worst case

E) It uses Θ(n^2) swaps in the average case

F) It uses Θ(n^2) swaps in the best case

Answer 1

Selection Sort:  Selection is a in place sorting algorithm. Selection sort work s like find minimum element in the array and move it to the start of the array like find the minimum element in the array and move it to 0 index and then check for next minimum in the remaining array which n-1 elements.After that find minimum element place it in 1 index and check in rest n-2 elements in the array and move to the first and continue this.

For any array we need to compare one element with all other elements so the time complexity and comparisions are n^2 in all the cases

SOLUITON: A, B, C

EXPLANATION OF ANSWER OPTIONS: A, B, C As explained above we need to compare every element with all other elements so the number of comparisions constant for all the cases that is n^2

EXPLANATION OF INCORRECT  OPTIONS:

D: Worst case is like all elements are not in correct order. In selection Sort we will sort at every pass in the array and we will swap at the end of the pass by finding minimum element so it is n-1 only so this option is  wrong

E: Average case is like some elements are in correct order like sorted order only so it is less than n-1 so this option is  wrong

F: Best case is like all are in correct order so number of swaps are 1 so this option is  wrong