PrepSnap logoPrepSnap
Pass

Question

1.
2.
3.
4.
Answer (Detailed Solution Below)

Option 2 : An already sorted array in strictly increasing order / पूर्णतः क्रमबद्ध वर्धमान ऐरे

Advertisement

Detailed Solution

सही उत्तर An already sorted array in strictly increasing order / पूर्णतः क्रमबद्ध वर्धमान ऐरे है।

Key Points
Helpful?
PrepSnapprepsnap.in • Part -A

Question:

With a first-element pivot, which input triggers quicksort's worst-case behaviour? / प्रथम-अवयव धुरी के साथ, कौन-सा इनपुट क्विकसॉर्ट का निकृष्टतम व्यवहार उत्पन्न करता है

1.
A randomly shuffled array / यादृच्छिक फेरबदल वाला ऐरे
2.
An already sorted array in strictly increasing order / पूर्णतः क्रमबद्ध वर्धमान ऐरे
3.
An array with all elements distinct but unsorted / सभी भिन्न पर अक्रमबद्ध अवयवों वाला ऐरे
4.
An array of just two elements / केवल दो अवयवों वाला ऐरे

Correct Answer: An already sorted array in strictly increasing order / पूर्णतः क्रमबद्ध वर्धमान ऐरे

On sorted input the first-element pivot always partitions off just one element, giving the recurrence T(n) = T(n−1) + O(n) = O(n²); random or arbitrary unsorted inputs avoid this degenerate split on average. / क्रमबद्ध इनपुट पर प्रथम-अवयव धुरी सदा केवल एक अवयव अलग करती है, जिससे T(n) = T(n−1) + O(n) = O(n²) प्राप्त होता है; यादृच्छिक या अक्रमबद्ध इनपुट औसतन इस अपभ्रष्ट विभाजन से बचते हैं।

Downloaded from PrepSnap (prepsnap.in)