recategorized
5,509 views
2 votes
2 votes

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
recategorized

2 Answers

Best answer
4 votes
4 votes
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
selected by
5 votes
5 votes

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

edited by
Answer:

Related questions

1 votes
1 votes
2 answers
1
1 votes
1 votes
1 answer
2
Arjun asked Apr 22, 2018
5,116 views
An array $A$ consists of $n$ integers in locations $A[0], A , \ldots A[n-1]$. It is required to shift the elements of the array cyclically to the left by $k$ places, wher...
3 votes
3 votes
1 answer
3
Arjun asked Apr 22, 2018
5,042 views
The following paradigm can be used to find the solution of the problem in minimum time:Given a set of non-negative integer and a value $K$, determine if there is a subset...
4 votes
4 votes
2 answers
4
Arjun asked Apr 22, 2018
3,848 views
Which of the following is application of Breath First Search on the graph?Finding diameter of the graphFinding bipartite graphBoth (a) and (b)None of the above