edited by
3,340 views
3 votes
3 votes

Of the following sort algorithms, which has execution time that is least dependant on initial ordering of the input?

  1. Insertion sort
  2. Quick sort
  3. Merge sort
  4. Selection sort
edited by

4 Answers

3 votes
3 votes

$\underline{\textbf{Answer:}\Rightarrow}\;\textbf{c.}$

$\underline{\textbf{Explanation:}\Rightarrow}$

In insertion sort, if the array is already sorted then it takes $\mathbf{O(n)}$. If the array is reverse sorted then it takes $\mathbf{O(n^2)}$.

In quick sort, if the array is already sorted or sorted in the reverse order, then it takes $\mathbf{O(n^2)}$.

The best and worst-case performance of the Selection sort is $\mathbf{O(n^2)}$ only.

But in case the array is already sorted then fewer swaps take place.

In the case of Merge Sort, the time complexity is always $\mathbf{O(nlogn)}$ for all the cases.

In short, Merge sort is Non-Adaptive in nature but rest of algorithms are.


$\underline{\text{Adaptive Sorting:}}$

If order of the elements to be sorted of an input array matters (or) affects the time complexity of a sorting algorithm, then that algorithm is called “Adaptive” sorting

edited by
0 votes
0 votes
option C)Merge sort ,as it is Non-adaptive in nature whereas other are adaptive in nature.

- If order of the elements to be sorted affects the time complexity of algorithm , then that algorithm is adaptive algorithm.
0 votes
0 votes
Option C is correct as merge sort and Heap sort are the only algorithms that don’t have any best or worst case.
Answer:

Related questions

5 votes
5 votes
5 answers
1
Satbir asked Jan 13, 2020
7,672 views
If an array $A$ contains the items $10,4,7,23,67,12$ and $5$ in that order, what will be the resultant array $A$ after third pass of insertion sort?$67,12,10,5,4,7,23$$4,...
3 votes
3 votes
3 answers
2
10 votes
10 votes
3 answers
3
Satbir asked Jan 13, 2020
8,560 views
What is the complexity of the following code?sum=0; for(i=1;i<=n;i*=2) for(j=1;j<=n;j++) sum++;Which of the following is not a valid string?$O(n^2)$$O(n\log\ n)$$O(n)$$O(...
5 votes
5 votes
2 answers
4
Satbir asked Jan 13, 2020
4,532 views
Huffman tree is constructed for the following data :$\{A,B,C,D,E\}$ with frequency $\{0.17,0.11,0.24,0.33\ \text{and} \ 0.15 \}$ respectively. $100\ 00\ 01101$ is decoded...