Register

UGC NET CSE | June 2019 | Part 2 | Question: 62

• edited by
2,986 views
3 votes
3 votes

There are many sorting algorithms based on comparison. The running time of heapsort algorithm is $O(n \text{lg}n)$. Like $P$, but unlike $Q$, heapsort sorts in place where $(P,Q)$ is equal to

  1. Merge sort, Quick sort
  2. Quick sort, insertion sort
  3. Insertion sort, Quick sort
  4. Insertion sort, Merge sort
• edited by
User Avatar

2 Answers

2 votes
2 votes

Answer should be (4) Insertion Sort, Merge Sort

Explanation - 

The question asks specifically for in-place sorting algorithms, which means the algorithms in which only $O(1)$ space is used. 

Hence, out of the options - 

Insertion Sort - Sorts in place with worst case time and space complexity of $O(n^2)$ and $O(1)$ respectively.

Heap Sort - Sorts in place with worst case time and space complexity of $O(n \cdot \log n)$ and $O(1)$ respectively.

Merge Sort - Sorts out of place with worst case time and space complexity of $O(n\cdot \log n)$ and $O(n)$ respectively. 

Quick Sort - Sorts in place with worst case time and space complexity of $O(n^2)$ and $O(1)$ respectively. 

 

Now for the given question, P needs to be an in place sorting algorithm, and Q needs to be out of place sorting algorithm, Hence option 4.

User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
2 answers
1
Arjun asked Jul 2, 2019
1,666 views
UGC NET CSE | June 2019 | Part 2 | Question: 61
Match List-I with List-II: ... ii) (a) - (ii); (b)-(i); (c)-(iv); (d)-(iii) (a) - (iii); (b)-(i); (c)-(iv); (d)-(ii)
Match List-I with List-II:$$\begin{array}{|c|c|c|c|} \hline {} & \text{List-I} & {} & \text{List-II} \\ \hline (a) & \text{Prim’s algorithm} & (i) & O(V^3 \log V) \\ \h...
User Avatar
7 votes
7 votes
3 answers
2
Arjun asked Jul 2, 2019
3,325 views
UGC NET CSE | June 2019 | Part 2 | Question: 64
Which of the following is best running time to sort $n$ integers in the range $0$ to $n^2-1$? $O(\text{lg } n)$ $O(n)$ $O(n\text { lg }n)$ $O(n^2)$
Which of the following is best running time to sort $n$ integers in the range $0$ to $n^2-1$?$O(\text{lg } n)$$O(n)$$O(n\text { lg }n)$$O(n^2)$
User Avatar
1 votes
1 votes
1 answer
3
Arjun asked Jul 2, 2019
1,881 views
UGC NET CSE | June 2019 | Part 2 | Question: 65
Which of the following is application of depth-first search? Only topological sort Only strongly connected components Both topological sort and strongly connected components Neither topological sort nor strongly connected components
Which of the following is application of depth-first search?Only topological sortOnly strongly connected componentsBoth topological sort and strongly connected components...
User Avatar
3 votes
3 votes
2 answers
4
Arjun asked Jul 2, 2019
4,000 views
UGC NET CSE | June 2019 | Part 2 | Question: 66
Consider double hashing of the form $h(k,i)=(h_1(k)+ih_2(k)) \text{mod m}$ where $h_{1}(k) = \text{k mod m} \ , \ \ h_{2}(k)=1+(\text{k mod n})$ where $n=m-1$ and $m=701$. For $k=123456$, what is the difference between first and second probes in terms of slots? $255$ $256$ $257$ $258$
Consider double hashing of the form$h(k,i)=(h_1(k)+ih_2(k)) \text{mod m}$ where $h_{1}(k) = \text{k mod m} \ , \ \ h_{2}(k)=1+(\text{k mod n})$ where $n=m-1$ and $m=701$....
User Avatar
Link Copied!