क्विक्सोर्ट - कौन सा उप-भाग पहले क्रमबद्ध किया जाना चाहिए?

Question

मैं कुछ पाठ जो इस दो पुनरावर्ती quicksort के आदेश के बारे में दावा है पढ़ रहा हूँ कॉल:

... यह पूंछ प्रत्यावर्तन के साथ संयोजन के रूप में यह पहली छोटे subproblem कॉल करने के लिए महत्वपूर्ण है, सुनिश्चित करता है कि ढेर गहराई लॉग एन है

मुझे यकीन नहीं है कि इसका मतलब क्या है, मुझे पहले छोटे उपरायरे पर क्विक्सोर्ट क्यों कहा जाना चाहिए?

Answer 1

आदर्श रूप से, सूची दो समान रूप से समान आकार के उपन्यासों में विभाजित है। इससे कोई फर्क नहीं पड़ता कि आप पहले किस तरह काम करते हैं।

लेकिन अगर एक बुरा दिन सबसे एकतरफा ढंग से सूची विभाजन संभव, दो या तीन आइटम, शायद चार, और एक sublist के sublist लगभग रूप में लंबे समय के रूप में मूल पर। यह विभाजन मूल्य या खराब रूप से प्रदूषित डेटा के खराब विकल्पों के कारण हो सकता है। कल्पना करें कि क्या होगा यदि आपने पहले बड़े उपन्यास पर काम किया था। क्विक्सोर्ट का पहला आविष्कार अपने स्टैक फ्रेम में छोटी सूची के लिए पॉइंटर्स/इंडेक्स धारण कर रहा है जबकि लंबी सूची के लिए रिकर्सल को क्विकोर्ट कॉल कर रहा है। यह भी बहुत कम सूची में बहुत बुरी तरह से विभाजन करता है, और हम पहले लंबे समय तक सब्सक्राइब करते हैं, दोहराते हैं ...

आखिरकार, दुष्ट डेटा के बुरे दिनों के बुरे दिनों में सबसे बुरे समय पर, हम ढेर होंगे मूल सूची लंबाई के आनुपातिक संख्या में निर्मित फ्रेम। यह quicksort का सबसे खराब मामला व्यवहार है, ओ (एन) रिकर्सिव कॉल की गहराई। (ध्यान दें कि हम रिकर्सन की गहराई की गहराई की बात कर रहे हैं, प्रदर्शन नहीं।)

छोटे sublist पहले करना इसे काफी जल्दी से छुटकारा पाता है। हम अभी भी मूल सूची की लंबाई के अनुपात में बड़ी संख्या में छोटी सूचियों को संसाधित करते हैं, लेकिन अब प्रत्येक को एक उथले एक या दो रिकर्सिव कॉल का ख्याल रखा जाता है। हम अभी भी ओ (एन) कॉल (प्रदर्शन) बनाते हैं लेकिन प्रत्येक गहराई ओ (1) है।

Answer 2

कुछ भाषाओं में पूंछ रिकर्सन है। इसका मतलब यह है कि यदि आप f (x) {... ... .. ... .. g (x)} लिखते हैं तो अंतिम कॉल, जी (x) को, फ़ंक्शन कॉल के साथ लागू नहीं किया गया है , लेकिन एक कूद के साथ, ताकि अंतिम कॉल किसी भी स्टैक स्पेस का उपयोग न करे।

क्विक्सोर्ट डेटा को दो वर्गों में क्रमबद्ध करने के लिए विभाजित करता है। यदि आप हमेशा पहले छोटे सेक्शन को संभालते हैं, तो स्टैक स्पेस का उपभोग करने वाले प्रत्येक कॉल में सॉर्ट करने के लिए डेटा का एक सेक्शन होता है जो इसे रिकर्सिव कॉल के आधे आकार का होता है। तो यदि आप सॉर्ट करने के लिए 10 तत्वों के साथ शुरू करते हैं, तो इसके गहरे भाग में ढेर में उन 10 तत्वों को सॉर्ट करने का कॉल होगा, और फिर अधिकतम 5 तत्वों पर कॉल सॉर्टिंग होगा, और उसके बाद अधिकांश 2 तत्वों पर कॉल सॉर्टिंग, और फिर कॉल सॉर्टिंग अधिकांश 1 तत्व - और फिर, 10 तत्वों के लिए, ढेर किसी भी गहरे नहीं जा सकते - स्टैक आकार डेटा आकार के लॉग द्वारा सीमित है।

यदि आप इसके बारे में चिंता नहीं करते हैं, तो आप 10 तत्वों को सॉर्ट करने वाले कॉल को ढेर कर सकते हैं, और उसके बाद कॉल 9 तत्वों को सॉर्ट कर सकते हैं, और उसके बाद कॉल 8 तत्वों को सॉर्ट कर सकते हैं, और इसी तरह, स्टैक सॉर्ट किए जाने वाले तत्वों की संख्या जितना गहरा था। लेकिन यदि आप पहले छोटे वर्गों को सॉर्ट करते हैं, तो यह पूंछ रिकर्सन के साथ नहीं हो सकता है, क्योंकि यद्यपि आप 10 तत्वों को 1 तत्व और 9 तत्वों में विभाजित कर सकते हैं, कॉल को 9 तत्वों को सॉर्ट करना आखिरकार किया जाता है और एक कूद के रूप में लागू किया जाता है, जो ' किसी और स्टैक स्पेस का उपयोग नहीं करते - यह पहले अपने कॉलर द्वारा उपयोग की जाने वाली स्टैक स्पेस का पुन: उपयोग करता है, जो कि वैसे भी वापस लौटने वाला था।

Answer 3

आश्चर्य की बात यह है कि यह तब भी महत्वपूर्ण हो जाता है जब क्विकॉर्ट को जंगली असंतुलित विभाजनों से सामना नहीं किया जाता है, और यहां तक ​​कि जब इंट्रोसोर्ट वास्तव में उपयोग किया जा रहा हो।

समस्या उत्पन्न होती है (सी ++ में) जब कंटेनर में क्रमबद्ध किए गए मान वास्तव में बड़े होते हैं।इसके द्वारा, मेरा मतलब यह नहीं है कि वे वास्तव में बड़ी वस्तुओं को इंगित करते हैं, लेकिन वे स्वयं वास्तव में बड़े हैं। उस स्थिति में, कुछ (संभवतः कई) कंपाइलर्स रिकर्सिव स्टैक फ्रेम को काफी बड़ा बना देंगे, क्योंकि स्वैप करने के लिए इसे कम से कम एक अस्थायी मान की आवश्यकता होती है। स्वैप को विभाजन के अंदर बुलाया जाता है, जो स्वयं ही रिकर्सिव नहीं होता है, इसलिए आपको लगता है कि क्विकॉर्ट रिकर्सिव ड्राइवर को राक्षस स्टैक-फ्रेम की आवश्यकता नहीं होगी; दुर्भाग्यवश, विभाजन आमतौर पर रेखांकित होता है क्योंकि यह अच्छा और छोटा होता है, और कहीं और से नहीं कहा जाता है।

आम तौर पर 20 और 40 स्टैक फ्रेम के बीच का अंतर नगण्य है, लेकिन यदि मूल्यों का वजन होता है, तो 8kb, तो 20 और 40 स्टैक फ्रेम के बीच का अंतर काम कर सकते हैं और स्टैक ओवरफ्लो के बीच का अंतर हो सकता है, यदि स्टैक्स में हैं कई धागे की अनुमति देने के लिए आकार में कम किया गया है।

आप "हमेशा छोटे विभाजन में recurse" एल्गोरिथ्म का उपयोग करते हैं, ढेर हर लॉग ऑन एन फ्रेम, जहां एन वेक्टर में तत्वों की संख्या है अधिक नहीं हो सकता। इसके अलावा, एन तत्व के आकार से विभाजित स्मृति की मात्रा से अधिक नहीं हो सकता है। तो एक 32-बिट मशीन पर, वहाँ केवल 2 एक सदिश में 8kb तत्व हो सकता है, और quicksort कॉल गहराई 19.

संक्षेप में, quicksort लेखन सही ढंग से अपने ढेर उपयोग करता है से अधिक नहीं हो सकता है उम्मीद के मुताबिक (जब तक आप एक स्टैक फ्रेम के आकार की भविष्यवाणी कर सकते हैं)। अनुकूलन के साथ परेशान कर रहा नहीं (एक भी तुलना को बचाने के लिए!) आसानी से ढेर गहराई भी गैर रोग के मामलों में दोगुना करने के लिए पैदा कर सकता है, और रोग मामलों में यह एक बहुत बदतर हो सकते हैं।

Answer 4

एक अंतर्निहित द्विआधारी पेड़ के रूप में quicksort देखें। पिवट रूट है, और बाएं और दाएं उपट्री आपके द्वारा बनाए गए विभाजन हैं।

अब विचार करना इस पेड़ की गहराई पहले खोज कर रही है। रिकर्सिव कॉल वास्तव में ऊपर वर्णित निहित पेड़ पर गहराई से पहली खोज करने के अनुरूप हैं। यह भी मान लें कि पेड़ में हमेशा छोटे बच्चे के रूप में छोटे उप-पेड़ होते हैं, इसलिए सुझाव वास्तव में इस पेड़ पर पूर्व-आदेश करने के लिए है।

अब मान लीजिए कि आप एक स्टैक का उपयोग करके प्रीऑर्डर लागू करते हैं, जहां आप केवल बाएं बच्चे को दबाते हैं (लेकिन माता-पिता को ढेर पर रखें) और जब सही बच्चे को धक्का देने का समय आता है (कहें कि आपने एक ऐसा राज्य बनाए रखा जहां आप जानते थे कि एक नोड, आप के बजाय सही बच्चे (इस पूंछ प्रत्यावर्तन भाग से मेल खाता) को आगे बढ़ाने का, ढेर के शीर्ष की जगह अपनी बाईं बच्चे का पता लगाया है या नहीं है)।

अधिकतम ढेर गहराई अधिकतम 'बाएं गहराई' है: यानी यदि आप प्रत्येक किनारे को बाएं बच्चे के रूप में 1 के रूप में चिह्नित करते हैं, और दाएं बच्चे को 0 के रूप में चिह्नित करते हैं, तो आप अधिकतम राशि के साथ पथ को देख रहे हैं किनारों (मूल रूप से आप दाएं किनारों की गणना नहीं करते हैं)।

अब चूंकि बाएं उप-पेड़ में तत्वों के आधे से अधिक तत्व नहीं हैं, हर बार जब आप बाएं जाते हैं (यानी ट्रैवर्स और एज 1 चिह्नित), तो आप कम से कम आधे से अन्वेषण करने के लिए छोड़े गए नोड्स की संख्या को कम कर रहे हैं।

इस प्रकार किनारों की अधिकतम संख्या में चिह्नित 1 कि आप देखते हैं, लॉग n से अधिक नहीं है।

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