In sorting algo which has a running time that is least dependent on initial ordering of inputs

Question

options

A. insertion

B. quick

C. selection

D. merge

Comments

#isro-2018

---

https://www.careerride.com/view/mcqs-on-sorting-with-answers-19637.aspx

(see Que 9 and Que 20)

here it is saying selection sort.

Answer 1

ans D

insertion sort : if the initial ordering is in reverse order it takes O(n²).

quick sort :if the initial ordering is in reverse order or sorted  it takes O(n²)

selection sort : best case and worst case O(n² ) it does not depend upon the order but swaping takes less (if sorted ) 

merge sort : in all cases O(nlogn) and its the ans ( i guess) 

Comments

but i think it should be selection sort bcz as in case of merge when input is already sort  then no. of omparision in case of merging will be less.

but in case of selection sort only 1 swap will take place and if sorted no swap or swap with itself

---

arjun sir plz give the ryt one

---

I have just one confusion that when the array is already sorted then there will be no swap operation in selection sort although copy operations would be there into merge sort into another array so I guess selection sort can also be the answer to it , plz clarify this .

---

In selection sort, you have to traverse whole array to find minimum, so even if swapping is not done, finding minimum will make it $O(n^2)$, so yes this is also a correct option along with merge sort.

Answer 2

option C,D

insertion sort: you must have played cards .its better to sort a hand rank wise if its not sorted .if its sorted already then no need to  sort it

quick sort:here the pivot element plays an important role.if the array is sorted and your algorithm  chooses the first element as pivot then you are going to get a worse case scenario

selection  sort:if its already sorted or not sorted it doesn't matter it always takes O(n^2)

merge sort:it too takes O(nlogn) time in any case