Hello दोस्तों, Gates Mashers में आपका स्वागत हैं इस वीडियो में हम डिस्क्रिश करने जा रहे हैं Quick Sort और इस वीडियो में हम Quick Sort से लेटिड सारे इंपोर्टेंट पॉइंट डिस्क्रिश करने जा रहे हैं जो आपके Competitive Exams या फिर आपके College या University लेवल के Exams के लिए और एवं आपकी Placements के लिए भी बहुत ज़्यादा इंपोर्टेंट है इट इस अ डिवाइड और कॉंकर टेक्नोलॉजी या डिवाइड और कॉंकर मेथड है अब ये डिवाइड और कॉंकर होता क्या है लेट से अगर मेरे पास एक प्रॉबलम है और प्रॉबलम का साइज है n तो हम करते क्या है डिवाइड और कॉंकर में बड़ी प्रॉबलम को सब प्रॉबलम में डिवाइड करते हैं फिर आगे n by 4, n by 4 इसको भी n by 4 है फिर हम उन सब problems को solve करते हैं, और finally हम उनका solution जो है वो, conquer, conquer मतलब combine करके, एक final answer जो है वो, देते हैं, तो जो quick sort है, ये भी partition based है, या आप कह सकते हो, ये भी जो है, ये भी जो है, डिवाइड करता है problem को, लेकिन ये कैसे डिवाइड करता है, कैसे partition करता है, ये सबसे ज़्यादा important है, और आपको कोई भी sorting algorithm आए न, किसी भी sorting algorithm की, या searching algorithm की बात करें, तो हमारे पास सिर्फ ये नहीं है कि वो काम कैसे करता है या उसका answer कैसे आएगा let's say अगर ये मैं आपको एक array दे दू unsorted array है आपको quick sort लगाना है आपसे ये थोड़े न पूछेंगे but will be the final output final output क्या होगी इसको आप sort करके लिख दो वो आपका final answer है सबसे पहले concept कि quick sort काम कैसे करता है दूसरा time complexity best case में average case में worst case में यह कैसे काम करता है इससे related और तीसरा recurrence relation क्योंकि recurrence relation आपको पता होगी कि कैसे लिखनी है तब ही आप time complexity जो है वो find out कर सकते हो क्योंकि substitution method या master method हम already discuss कर चुके हैं तो यहाँ पे start करते हैं सबसे पहले कि काम कैसे करता है हमने यहाँ पे normal जो है वो एक unsorted array लिया है तो देखो सबसे पहले काम कैसे करता है यह पहले element को हम इसको क्या दे देते हैं पाइवट एलिमेंट का नाम दे देते हैं, मतलब ये मेरा क्या है, पाइवट एलिमेंट है, अब ये पाइवट एलिमेंट को हमने यहाँ पर रिजर्व कर दिया, और हमने यहाँ पर ले लिये दो पॉइंटर, एक है पॉइंटर P, और एक है पॉइंटर Q, अब जो P पॉइं पाइवट ये सारे पॉइंट आप लिखते रहना जो ये कब रुकेगा ये move करेगा एक एक करके ऐसे right hand side लेकिन ये कब रुकेगा जब इसको element मिलेगा greater than the pivot element तो इस रिके से move करता रहेगा ऐसे क्यूं क्यूं जो है वो decrement करता जाएगा मतलब LHS की तरफ move करता जा रहा है और ये कब रुकेगा जब इसको element मिलेगा lesser than the pivot element अब ये करते क्यों है अब ये P actual में करना क्या जाता है कि pivot element के right side में सारे बड़े elements आ जाएं, और left side में सारे छोटे आ जाएं, तो छोटे लाने के लिए, Q help करेगा, और right side में सारे बड़े elements लाने के लिए, P help करेगा, आपको further समझ आ जाएगा, कि actual में क्या कर रहे हैं, अब देखो, P एक एक करके move करेगा, last में हमने plus infinite यहाँ पर लगाना है, कि plus infinite क्यों लगाते हैं, देखो, let's say अगर आपका array इस तरीके से है, 35, 5, 4, 3, 2, 1 इस तरीके से for example अब देखो 35 ये मेरा pivot है 5, 5 greater than है? नहीं है next move करो कब रुकेगा जब greater मिलेगा 4 greater than है? नहीं next move करो 3, नहीं, 2, नहीं 1, नहीं तो ये कब रुकेगा इसको stop भी तो कर रहे है ना तो इसको stop करने के लिए हमने यहाँ पे plus infinity लिख दिया because plus infinite obviously greater होगा किस से?
pivot elements है मतलब यहाँ पे आके यह रुक जाएगा garbage value देगा तो यानि यह stop करने के लिए हमने यहाँ पे लिखे है अब कई बार question आता है कि sir q को अगर हमने left side में बढ़ा रहे हैं तो q को भी तो stop करना पड़ेगा तो क्या यहाँ पे मैं minus infinity लिखो? नहीं q जो है वो जब next यहाँ पे decrement करेगा तो actually में वो क्या check कर रहा है? less than equal to मतलब pivot element से less than equal to यह चेक कर रहा है greater than equal to अब देखो greater than equal to obviously pivot element तो इसके left में है और यह आगे आगे बढ़ता जा रहा है तो pivot तो कभी आएगा ही नहीं लेकिन q जो है वो pivot की तरफ आ रहा है अब q अगर pivot की तरफ आ रहा है तो देखो less than equal to less than equal to तो pivot के तो बराबर होगा ही ना तो यानि इससे next ये move करेगा ही नी तो कम से कम pivot पे तो ये automatically रुक जाएगा तो ये actual में concept है P और Q Q हम कैसे move करते हैं, अब let's start with the concept, let's say P हम सबसे पहले start कर रहे हैं, P, 50, 50 greater than 35, yes, stop, आगे move ही नहीं करना, next आजो Q पे, Q 45, 45 less than 35, no, तो Q को आगे move करो, 90, 90 less than 35, no, तो आगे move करो, 20, 20 less than 35, yes, stop हो गया, Q यहाँ पे stop है, P already यहाँ पे stop है, अब यह आपको check करना है कि क्या P और Q ने आपस में interchange कर लिया, मतलब P और Q आपस में cross तो नहीं हुए, नहीं, P और Q अभी तक cross नहीं हुए, तो आपको simply करना क्य कर दो इन दोनों की position पे जो भी element है उनको swap कर दो मतलब आपकी जो output है वो इस तरीके से आएगी अब 20 यहाँ पे आ गया 15 as it is 25 as it is 80 as it is 20 की जगह क्या आ गया 50 90 45 plus infinite इस तरीके से जो है वो आपका अब आएगा तो अब देखो P जो है यहाँ पे था Q जो है वो इस position पे था, अब फिर बढ़ाओ, next, p, p greater than, मतलब 15 greater than 35, no, 25, 25 greater than 35, no, 80, 80 greater than 35, yes, stop p, p को यहाँ पे stop कर दिया, लेकिन q को भी सासा चलाना है, लेकिन मैं एक एक करके चला रहा हूँ, आपको q को भी बराबर चलाना है, q, 50, less than 35, no, next, 80, 80 less than 35, no, next, 25, 20, 25 less than 35, yes, तो Q यहाँ पे stop हो गया, P यहाँ पे, अब आपको check करना है कि क्या P और Q ने आपस में एक दूसरे को cross कर लिया, यहाँ P था, यहाँ Q था, इसमें नहीं किया था, लेकिन आप देखो P और Q आपस में cross कर चुके हैं, Q इधर आ गया, P इधर आ गया, जब भी इस type का situation पाइवट एलिमेंट को रिप्लेस कर देना है, किसके साथ? Q वाले एलिमेंट के साथ, याद रखना, Q जिसको भी पॉइंट आउट कर रहा है, उस एलिमेंट के साथ आप स्वैप कर दो पाइवट को, मतलब 25 यहां �� गया, 20 यहां, 15 यहां, 35 यहां, Q कहां पे पॉइंट आउ जब इन्होंने cross नहीं किया, या बराबर नहीं आए, लेकिन अगर ये बराबर आगे, या cross कर गए, तो अब आपको pivot के साथ करना है, rest of the element same, 80, 50, 90, 40, 5, clear point, तो ये actual में concept है यहाँ पे, अब देखो, 35 आपका, ये इसको बोलते हैं, one pass, मतलब ये first pass था, first step था, first step complete होते ही, आपका जो pivot element है, वो right position पे पहुँच गया, देखो 35 right position है, 35 से सारे चोटे इदर है, 35 से सारे बड़े इदर है, sort नहीं हुआ भी, अभी तो एक step हुआ है, लेकिन इस step के बाद, 35 अपनी right position पे पहुँच गया, और इससे जो चोटे है वो इदर है, इससे जो बड़े है वो इदर है, यानि आपने इस problem को 2 part में divide कर दिया, 25, 20, 15 इदर आ गया, 80, 50, 90, 45 अग, इस तरफ आ गया और आपका जो 35 pivot है वो आपका right position पे पड़ है अब आपकी जो problem है वो दो parts में divide होगी अब इदर भी लगाओ quick sort इदर भी लगाओ quick sort अब इदर अगर मैं लगाता हूँ quick sort तो क्या होगा 25 is the pivot element तो 25 जो है वो मेरा pivot element है P आपका ये रहा Q आपका ये रहा simple जैसे हमने P greater than 25 no आगे move करो 15 greater than 25, no, आगे move करो, आगे क्या है, plus infinite, तो plus infinite पे क्या रुख गया, P रुख गया, यहाँ से निकल गया, P और यहाँ रुख गया, Q को भी check करना है, 15 less than 25, yes, यहाँ पे रुखे रो, क्योंकि Q जो है, Q वाला element less है, तो यह stop रहेगा, अब आप check करो, क्या P और Q आपस में cross कर चुके हैं, cross कर चुके हैं, जब यह दोनों आपस में cross कर चुके हैं, मैंने क्या बताया, पाइवट एलिमेंट को क्यू वाले के साथ exchange कर दो, तो देखो, 15 आगे आगया, 20 as it is, 25 यह रहा, और यहाँ पे जो पाइवट है, वो आप as it is 35 को कुछ नहीं करना, वो as it is है, तो देखो यह वाला जो सब area है, वो sorted हो गया, same अब हमने यहाँ पे करना है, 80 आपका पाइवट था, PR, आपका ये रहा, Q आपका ये रहा, और plus infinity यहाँ, यह actually में इस दो parts में divide हो गया न, तो ये अलग चल रही है, ये अलग चल रही है, तो same यहाँ पे, P, 50 greater than 80, no, next move करो, 90 greater than 80, yes, तो P आपका आप किसको point करेगा, 90 को, same ऐसे, 45 less than 80, yes, Q आपका यहीं पे रुका रहेगा, तो क्या P और Q आपस में cross हुए, नहीं हुए, तो इस case में हमने इन दोनों को swap करना है, पाइवर्ट से कुछ लेना देना नहीं है, मतलब इन दोनों को जो स्वैप किया, तो मैं यहाँ पर लिख देता हूँ, 80, 50, 45, 90, that's it, अभी P यहाँ पर था, Q यहाँ पर था, और plus infinity as it is अब आपको देखो next 90 90 greater than 80 yes तो आपका P जो है वो इस point पे stop कर गया Q चेक करो Q 90 less than no next आजाएगा Q 45 less than 80 45 less than 80 है yes तो Q यहाँ पे stop कर गया Q less चेक कर रहा है वो greater तो देखो दोनो position आपस में क्या कर चुके है cross कर चुके है P और Q आपस में cross कर चुके है अगर यह cross कर चुके है Q की जगा pivot element को लिख दो, तो यानि, Q जो है वो 45 वो pivot की जगा आ गया, 50 as it is, और Q वाली position पे pivot, pivot कौन सा था, 80, 80 यहां आ गया, 90 as it is, तो देखो overall आपका जो array है, वो क्या हो चुक है, sorted हो चुक है, तो इस तरीके से actual में, quick sort जो है वो काम करता है, यह normal case है, मतलब average case या best case कह लो, हमने अभी worst case की यहाँ पे कोई बात नहीं की, तो normal case में, अगर आपका problem जो है वो, उसका size n है, तो अगर आपका जो pivot element है, अक्शन में सारी कहानी pivot element के उपर depend करती है, कि pivot element कहां पे जाके बैठेगा, first pass के बाद, अगर आपका pivot element, बिल्कुल middle में, मतलब, let's say यह मेरी n size है, first pass के बाद, n by 2, n by 2 minus 1, यह minus 1 क्यों किया, क्योंकि pivot element ही यह रहा, मतलब on an average आप कह सकते हो, दो parts में divide होगी, अब ऐसी n by 4, n by 4, n by 4, n by 4, इस तरीके से divide हो रही है, तो यानि आप क्या सके सकते हो, कि मेरी जो problem है, अगर मेरी problem t of n है, तो यह divide हो रही है, n by 2 plus n by 2, दो parts में divide हो रही है, plus n time जो है, वो यहाँ पे लग रहा है, n time क्या लग रहा है, हर एक step में, पहले pass को जब आपने किया, इस step को complete किया, तो आपको पूरा array scan करना पड़ा, तब जाके आपका एक pass complete हुआ है, पूरा array आपने scan किया, तब आपका एक pass complete हुआ है, तो this n time is for the scanning entire array, क्योंकि array का size कितना है maximum?
n, तो यानि आपका जो actual में reconciliation हो क्या आ गया? 2tn by 2 plus n, this is the final reconciliation in the average case, normal तो अगर आप इसको solve करो हम अलड़ी कर चुके हैं master method भी और even substitution method भी अगर आप solve करोगे तो answer क्या आएगा n log n तो that's why the average case time complexity of quick sort is n log n तो next video में हम बात करेंगे worst case time complexity Thank you