ISRO CSE 2018 | Question: 66

Question

Of the following sorting algorithms, which has a running time that is least dependent on the initial ordering of the input?

1. Mege Sort
2. Insertion Sort
3. Selection Sort
4. Quick Sort

Answer 1

Answer will be Merge Sort

In merge sort we divide the array in 2 subarrays, then again divide it in 2 subarrays, like that it divide entire array

And time of merging, we merge 2 subarrays, again merge next two sub arrays

So, here input hardly matters to sort the array

But if we consider quick sort , here initial ordering matters. Because if the array is increasing or decreasing order , quick sort takes maximum running time to find, is the array is sorted or not

Similarly, for insertion sort and selection sort, for sorted and unsorted input running time differs in every case

Comments

Since when selection sort time depends on input?

---

How selection sort depends upon input?

---

Please explain how selection sort depends on the input?

As far I know ,In best as well as worst case the number of swaps are same.

---

Selection Sort always performs O(n^2) comparisons regardless of the initial order. While it does not change its asymptotic running time between best and worst cases, it is not considered "least dependent on initial ordering" in the practical sense. This is because even though its running time is consistent, it's consistently inefficient compared to Merge Sort. The question is asking for the algorithm whose performance is robust and efficient regardless of the input order—and that is Merge Sort.

I think even though Selection Sort has the same O(n^2) complexity for any input order, Merge Sort is both efficient and independent of the input order, making it the best answer.

Answer 2

option a

merge sort---> best and worst time complexity o(nlogn). it dosent depend ordering of input. .like array is sorted or not.

quick sort---> if array is sorted then time complexity is o(n^2) and if array is not sorted then it will take o(nlogn).so it depend upon ordering of input.

insertion sort--->  if array is sorted then time complexity is o(n) and if array is not sorted then it will take o(n^2).so it depend upon  ordering of input.

selection sort -----> best and worst time complexity is o(n^2). i think it also dosent depend upon ordering of input.

but i marked option a

Comments

why not selection sort?

---

The reason why not selection sort becoz, the number of swaps depends on initial ordering of the array, however it's time complexity is same for all cases becoz of the number of comparisions are same in all cases