Quick Sort Lecture Notes

परिचय

• Quick Sort पर चर्चा
• प्रतियोगी परीक्षा, कॉलेज/यूनिवर्सिटी लेवल परीक्षा और प्लेसमेंट के लिए महत्वपूर्ण
• यह "डिवाइड और कॉंकर" तकनीक पर आधारित है

डिवाइड और कॉंकर तकनीक

• बड़ी समस्या को छोटे हिस्सों में विभाजित करना
• छोटे हिस्सों को हल करने के बाद, उनके समाधान को संयोजित करना

Quick Sort का कार्य

• यह भी समस्या को विभाजित करता है
• मुख्य बात: कैसे विभाजित करता है और कैसे पार्टिशन करता है

Sorting Algorithm और Searching Algorithm

• केवल अंतिम परिणाम नहीं, बल्कि प्रक्रिया को समझना भी आवश्यक है

Quick Sort प्रक्रिया

1. **पार्टीशनिंग:
   • पहले तत्व को "पिवट" माना जाता है
   • दो पॉइंटर्स: P (दाए) और Q (बाएँ)
     **
2. **P और Q की स्थिति:
   • P दाहिनी तरफ बढ़ता है जब तक कि पिवट से बड़ा तत्व नहीं मिल जाता
   • Q बाईं तरफ बढ़ता है जब तक कि पिवट से छोटा तत्व नहीं मिल जाता
     **
3. **स्वैपिंग:
   • जब P और Q की स्थिति क्रॉस नहीं होती, तो स्वैप करें
   • यदि क्रॉस हो गए हैं, तो पिवट को Q के स्थान पर रख दें
     **

एक उदाहरण

• उच्चतम स्थिति में, पिवट तत्व को सही स्थिति पर ले जाना
• पहले पास में पिवट तत्व को सही स्थान पर रखा जाएगा
• इसके बाद पुनरावृत्ति की जाती है

टाइम कॉम्प्लेक्सिटी

• सर्वश्रेष्ठ और औसत केस में O(n log n)
• यदि पिवट संतुलित ढंग से विभाजित करता है, तो यह सबसे अच्छा प्रदर्शन करता है
• समय की जटिलता गणना करने के लिए पुनरावृत्ति संबंध

Recurrence Relation

• यदि समस्या का आकार n है, तो इसे n/2, n/2 में विभाजित किया जा सकता है
• समय जटिलता: T(n) = 2T(n/2) + O(n)
• इसको हल करने पर O(n log n) प्राप्त होता है

निष्कर्ष

• Quick Sort का औसत केस समय जटिलता O(n log n) है
• अगली वीडियो में, हम Worst Case टाइम कॉम्प्लेक्सिटी पर बात करेंगे

धन्यवाद

• वीडियो देखने के लिए धन्यवाद!