Question
1.
2.
3.
4.
Answer (Detailed Solution Below)
Option 2 : Heap sort
Advertisement
Detailed Solution
सही उत्तर Heap sort है।
Key Points
Helpful?
prepsnap.in • Part -AQuestion:
Which sorting algorithm guarantees $O(n \log n)$ worst-case time complexity with $O(1)$ auxiliary space? / कौन-सा सॉर्टिंग एल्गोरिदम $O(n \log n)$ worst-case समय जटिलता और $O(1)$ सहायक स्थान की गारंटी देता है?
1.
Merge sort
2.
Heap sort
3.
Quick sort
4.
Insertion sort
Correct Answer: Heap sort
Heap sort builds a heap in place and repeatedly extracts the maximum, giving $O(n \log n)$ time in all cases with only $O(1)$ extra space. Merge sort needs $O(n)$ extra space and quick sort degrades to $O(n^2)$ in the worst case. / हीप सॉर्ट हीप को स्थान पर बनाता है और बार-बार अधिकतम निकालता है, जिससे सभी स्थितियों में $O(n \log n)$ समय और केवल $O(1)$ अतिरिक्त स्थान मिलता है। मर्ज सॉर्ट को $O(n)$ अतिरिक्त स्थान चाहिए और क्विक सॉर्ट worst-case में $O(n^2)$ हो जाता है।
Downloaded from PrepSnap (prepsnap.in)