पायथन क्विकसॉर्ट कैसे कोड करें

पायथन क्विकसॉर्ट कैसे कोड करें

पायथन क्विकसॉर्ट एक पिवट तत्व का चयन करता है और ऐरे के तत्वों को दो नए ऐरे में विभाजित करता है। पिवट से अधिक संख्याएं एक ऐरे में जाती हैं; पिवट से कम संख्याएं दूसरी में जाती हैं। प्रत्येक ऐरे को सॉर्ट किया जाता है और फिर सभी ऐरे को एक में मिला दिया जाता है।

पायथन क्विकसॉर्ट कैसे कोड करें

प्रोग्रामिंग में सूची को सॉर्ट करने के लिए आप बहुत सारे सॉर्टिंग एल्गोरिदम का उपयोग कर सकते हैं। पायथन इंसर्शन सॉर्ट्स, बबल सॉर्ट्स, और बहुत कुछ हैं। क्विकसॉर्ट सबसे सामान्य प्रकार के सॉर्ट्स में से एक हैं।

इस गाइड में, हम बात करेंगे कि क्विकसॉर्ट क्या हैं और वे कैसे काम करते हैं। हम पायथन क्विकसॉर्ट के एक उदाहरण के माध्यम से चलेंगे ताकि आप सीख सकें कि इसे कैसे लागू किया जाए।

बिना किसी देरी के, चलो शुरू करते हैं!

पायथन क्विकसॉर्ट क्या है?

पायथन क्विकसॉर्ट एल्गोरिदम एक ऐरे को उप-सरणियों में विभाजित करता है। यह एल्गोरिदम सूची में प्रत्येक तत्व को सॉर्ट करने के लिए इन उप-सरणियों को पुनरावर्ती रूप से कॉल करता है। उप-सरणी की सामग्री एक पिवट तत्व द्वारा निर्धारित की जाती है जिसे नई उप-सरणी में नहीं ले जाया जाता है।

क्विकसॉर्ट एल्गोरिदम विभाजित-और-जीतो (divide-and-conquer) का उपयोग करता है। इसका मतलब है कि सूची को सॉर्ट करने का कार्य कई उप-कार्यों में विभाजित हो जाता है। सॉर्ट के अंत में, इन उप-कार्यों के परिणाम एक सॉर्ट की गई सूची लौटाने के लिए एक साथ आते हैं।

क्विकसॉर्ट में, उप-कार्य प्रत्येक उप-सूची के लिए पिवट सेट करना और तत्वों को पिवट के सापेक्ष उनके मूल्य के आधार पर क्रमबद्ध करना है।

मुझे पायथन क्विकसॉर्ट कब उपयोग करना चाहिए?

क्विकसॉर्ट तब उपयोगी होता है जब समय जटिलता मायने रखती है। ऐसा इसलिए है क्योंकि क्विकसॉर्ट अन्य एल्गोरिदम की तुलना में कम मेमोरी स्पेस का उपयोग करते हैं, जो उन्हें दक्षता बढ़ावा देता है।

आपको केवल क्विकसॉर्ट का उपयोग करना चाहिए यदि आप पायथन पुनरावृत्ति से परिचित हैं। ऐसा इसलिए है क्योंकि क्विकसॉर्ट एल्गोरिदम पुनरावर्ती फ़ंक्शंस पर निर्भर करता है।

क्विकसॉर्ट छोटे ऐरे पर मर्ज सॉर्ट की तुलना में अधिक कुशल है। हालांकि, बड़े डेटा सेट पर, इंसर्शन सॉर्ट या मर्ज सॉर्ट तेज़ हो सकते हैं।

क्विकसॉर्ट कैसे काम करता है?

क्विकसॉर्ट पिवट के रूप में कार्य करने के लिए एक तत्व चुनता है। यह सूची में कोई भी तत्व हो सकता है। इस ट्यूटोरियल के लिए, हम सूची में अंतिम आइटम (3) चुनने जा रहे हैं।

क्विकसॉर्ट पिवट के मान की तुलना सूची में आइटम्स के माध्यम से लूप करते समय हर संख्या से करता है। यदि कोई आइटम पिवट संख्या से बड़ा है, तो हम संख्या को पिवट के बाद ले जाते हैं; अन्यथा, हम संख्या को पिवट से पहले ले जाते हैं:

मान 3 हमारी सूची में नीचे चला गया है। 3 से कम सभी आइटम्स इसके बाईं ओर चले गए; तीन से अधिक सभी मान इसके दाईं ओर चले गए।

हमारा पायथन ऐरे दो हिस्सों में विभाजित है: पिवट से अधिक आइटम्स और पिवट से कम आइटम्स।

एक बार यह प्रक्रिया शुरू हो जाने पर, प्रत्येक दो हिस्सों पर एक नया पिवट शुरू होता है। यह पिवट अलग से शुरू होता है और ऊपर दिए गए समान एल्गोरिदम का उपयोग करता है। पहले, हम एक पिवट मान सेट करेंगे जो प्रत्येक सूची में अंतिम मान के बराबर है:

अगला, हम पिवट से अधिक सभी मानों को पिवट के दाईं ओर ले जाएंगे। हम पिवट से कम सभी मानों को बाईं ओर ले जाएंगे।

यह प्रक्रिया तब तक जारी रहती है जब तक हम अपनी सूची को सॉर्ट नहीं कर लेते:

हमारा अंतिम ऐरे इस तरह दिखता है:

पायथन क्विकसॉर्ट उदाहरण

क्विकसॉर्ट को दो फ़ंक्शंस की आवश्यकता होती है: एक पार्टिशन फ़ंक्शन और एक क्विकसॉर्ट फ़ंक्शन।

आइए पार्टिशन फ़ंक्शन से शुरू करते हैं। यह पिवट तत्व के मूल्य के आधार पर ऐरे को पार्टिशन या तैयार करेगा।

हमारा पार्टिशन फ़ंक्शन करेगा:

1. पिवट तत्व का चयन करें
2. पिवट से अधिक सभी आइटम्स को पिवट के दाईं ओर ले जाएं
3. पिवट से कम सभी आइटम्स को पिवट के बाईं ओर ले जाएं

क्विकसॉर्ट पायथन प्रोग्राम

आइए एक प्रोग्राम लिखें जो इस एल्गोरिदम को लागू करता है:

def prepare(numbers, low, high):
    pivot = numbers[high]
    item = low - 1
    for i in range(low, high):
        if numbers[i] <= pivot:
            item = item + 1
            (numbers[item], numbers[i]) = (numbers[i], numbers[item])
    (numbers[item + 1], numbers[high]) = (numbers[high], numbers[item + 1])
    return item + 1

सबसे पहले, हम एक पिवट तत्व का चयन करते हैं। यह हमारी सूची में सबसे बड़ी संख्या के बराबर है।

अगला, हम पायथन फॉर लूप का उपयोग करके सूची में सभी आइटम्स के माध्यम से लूप करते हैं। यदि कोई संख्या पिवट से कम या बराबर है, तो इसे पिवट के बाईं ओर ले जाया जाता है। अन्यथा, यह पिवट के दाईं ओर जाता है।

हमारा पायथन फ़ंक्शन नया उच्च मान लौटाता है। नया उच्च मान item + 1 के बराबर है।

अगला, हमें अपने एल्गोरिदम को चलाना होगा। हम एक अलग फ़ंक्शन लिखकर ऐसा कर सकते हैं:

def quick_sort(numbers, low, high):
    if low < high:
        pivot = prepare(numbers, low, high)
        quick_sort(numbers, low, pivot - 1)
        quick_sort(numbers, pivot + 1, high)

यह फ़ंक्शन जांचता है कि "low" का मान "high" के मान से कम है या नहीं। यदि यह है, तो हमारा सॉर्ट जारी रह सकता है। अन्यथा, हमारा सॉर्ट रुक जाता है। यदि हमारा सॉर्ट रुक जाता है, तो इसका मतलब है कि हमने सूची को सॉर्ट कर लिया है।

अगला, हमारा फ़ंक्शन prepare() विधि को कॉल करता है। यह पिवट के लिए एक पॉइंटर पहचानता है और आइटम्स को उनकी सही जगह पर ले जाता है।

हमारा फ़ंक्शन फिर quick_sort() विधि को दो बार कॉल करता है। पहली बार, हम पिवट के बाईं ओर के तत्वों पर क्विकसॉर्ट चलाते हैं। दूसरी बार, हम पिवट के दाईं ओर के तत्वों पर क्विकसॉर्ट चलाते हैं। इसलिए, हमारा फ़ंक्शन पुनरावर्ती है क्योंकि यह स्वयं को कॉल करता है।

यह तब तक जारी रहता है जब तक सूची में प्रत्येक आइटम सॉर्ट नहीं हो जाता।

मुख्य विधि लिखना

आइए एक मुख्य प्रोग्राम लिखें जो सॉर्ट की जाने वाली सूची को परिभाषित करता है:

values = [8, 4, 5, 2, 1, 3]
total_values = len(values)
quick_sort(values, 0, total_values - 1)
print(values)

सबसे पहले, हम सॉर्ट करने के लिए मानों की सूची निर्दिष्ट करते हैं। हम अपने मानों की सूची की लंबाई की गणना करने के लिए पायथन len() विधि का उपयोग करते हैं। अगला, हम quick_sort() विधि को कॉल करते हैं।

हम "values" को उन संख्याओं के रूप में पास करते हैं जिन्हें हम सॉर्ट करना चाहते हैं। फिर हम 0 को कम संख्या के रूप में पास करते हैं। "values" की लंबाई माइनस 1 वह उच्च मान है जिसे हम निर्दिष्ट करते हैं। उच्च मान values की लंबाई माइनस 1 है क्योंकि सूची में पहले आइटम का इंडेक्स नंबर 0 होता है।

आइए अपना प्रोग्राम चलाने का प्रयास करें:

[1, 2, 3, 4, 5, 8]

हमारा कोड सॉर्ट की गई सूची लौटाता है! हमने कर दिखाया। अपनी पीठ थपथपाएं। क्विकसॉर्ट समझने या लागू करने में आसान नहीं हैं।

जटिलता अवलोकन

औसतन, यह एल्गोरिदम O(n* log n) पर प्रदर्शन करेगा। यह तब होता है जब पिवट तत्व सबसे बड़ा या सबसे छोटा तत्व नहीं होता है और जब पिवट तत्व मध्य तत्व के निकट नहीं होता है।

क्विकसॉर्ट की सबसे खराब स्थिति जटिलता O(n²) है। यह तब होता है जब पिवट के रूप में चुना गया तत्व या तो सबसे बड़ा या सबसे छोटा तत्व होता है। यदि ऐसा है, तो पिवट तत्व हमेशा सॉर्ट की गई ऐरे के अंत में होगा। यह अनावश्यक उप-सरणियों की संख्या बनाएगा।

इस एल्गोरिदम के लिए सर्वोत्तम स्थिति जटिलता O(n* log n) है। यह तब होता है जब पिवट तत्व या तो मध्य तत्व के बराबर होता है या मध्य तत्व के निकट होता है।

एल्गोरिदम जटिलता के बारे में अधिक जानने के लिए, बिग O नोटेशन पर हमारी गाइड देखें।

निष्कर्ष

पायथन क्विकसॉर्ट पुनरावृत्ति का उपयोग करके सूची को छोटी सूचियों में विभाजित करता है जिन्हें फिर सॉर्ट किया जाता है। प्रत्येक सूची को पिवट तत्व के चारों ओर सॉर्ट किया जाता है। पिवट से बड़े तत्वों को इसकी दाईं ओर ले जाया जाता है; छोटे तत्वों को पिवट के बाईं ओर ले जाया जाता है।

शीर्ष पायथन सीखने के संसाधनों, ऑनलाइन पाठ्यक्रमों, और पुस्तकों पर मार्गदर्शन के लिए, हमारा संपूर्ण How to Learn Python गाइड पढ़ें।