What is the time complexity of the Quicksort algorithm?

Explanation / व्याख्या :

• Quicksort is a divide-and-conquer sorting algorithm. In the average and best cases, it divides the array into two parts and sorts them recursively, which gives it a time complexity of O(n log n).
  Quicksort एक डिवाइड-एंड-कॉन्कर सॉर्टिंग एल्गोरिथ्म है। औसत और सर्वश्रेष्ठ मामलों में, यह ऐरे को दो भागों में बाँटता है और उन्हें पुनरावर्ती तरीके से सॉर्ट करता है, जिससे इसका टाइम कॉम्प्लेक्सिटी O(n log n) होता है।

• In the worst case, when the pivot is always the smallest or largest element, the time complexity becomes O(n²).
  सबसे खराब स्थिति में, जब पिवट हमेशा सबसे छोटा या सबसे बड़ा तत्व होता है, टाइम कॉम्प्लेक्सिटी O(n²) हो जाती है।

• Other options are incorrect:

  • O(n²) → Only occurs in the worst-case scenario.
    O(n²) → केवल सबसे खराब स्थिति में।

  • O(n) → Incorrect; Quicksort cannot sort in linear time for arbitrary inputs.
    O(n) → गलत; Quicksort किसी भी इनपुट के लिए रैखिक समय में नहीं सॉर्ट कर सकता।

  • O(log n) → Incorrect; logarithmic time is not sufficient to sort all elements.
    O(log n) → गलत; लॉगरिदमिक समय सभी तत्वों को सॉर्ट करने के लिए पर्याप्त नहीं है।

Extra Facts / अतिरिक्त तथ्य:

• Quicksort is in-place, meaning it doesn’t require additional arrays for sorting.
  Quicksort इन-प्लेस है, यानी सॉर्टिंग के लिए अतिरिक्त ऐरे की जरूरत नहीं होती।

• It is generally faster in practice than other O(n log n) algorithms like Merge Sort due to low constant factors.
  Merge Sort जैसे अन्य O(n log n) एल्गोरिथ्म की तुलना में यह अमल में तेज़ होता है, क्योंकि इसके कॉन्स्टेंट फैक्टर्स कम होते हैं।

• The choice of pivot element (first, last, random, or median) greatly affects the performance.
  पिवट एलिमेंट (पहला, आखिरी, रैंडम या मीडियन) का चयन प्रदर्शन को काफी प्रभावित करता है।