त्वरित प्रकार की पुनरावृत्तियों की आवश्यकता

Question

tl; dr: क्या एक दोगुनी लिंक्ड सूची पर क्विकॉर्ट को प्रभावी ढंग से कार्यान्वित करना संभव है? इसके बारे में सोचने से पहले मेरी समझ थी, नहीं, इसकी नहीं।

दूसरे दिन मुझे मूल सॉर्टिंग एल्गोरिदम के लिए इटरेटर आवश्यकताओं पर विचार करने का अवसर मिला। मूल ओ (एन²) एक काफी सरल हैं।

• बबल सॉर्ट - 2 आगे इटेटरेटर अच्छी तरह से करेंगे, एक दूसरे के बाद खींच रहा है।
• सम्मिलन क्रम - 2 बिडरेक्शनल इटरेटर करेंगे। आउट ऑफ़ ऑर्डर तत्व के लिए एक, सम्मिलन बिंदु के लिए एक।
• चयन क्रम - थोड़ा सा ट्रिकियर लेकिन आगे इटेटरेटर चाल कर सकते हैं।

quicksort

std :: प्रकार में introsort_loop (जीएनयू मानक पुस्तकालय/अश्वशक्ति (1994) के रूप में/सिलिकॉन ग्राफिक्स (1996)) ऐसा करना आवश्यक हो random_access किया जाना है।

__introsort_loop(_RandomAccessIterator __first, 
     _RandomAccessIterator __last, 
     _Size __depth_limit, _Compare __comp) 

जैसा कि मैंने अपेक्षा की है।

अब नज़दीकी निरीक्षण पर मुझे क्विकॉर्ट के लिए इसकी आवश्यकता के वास्तविक कारण नहीं मिल सकते हैं। केवल एक चीज जो स्पष्ट रूप से random_access_iterators की आवश्यकता है std::__median कॉल है जिसके लिए मध्य तत्व की गणना की आवश्यकता होती है। नियमित, वेनिला क्विकॉर्ट औसत की गणना नहीं करता है।

विभाजन एक चेक

if (!(__first < __last)) 
    return __first; 

नहीं वास्तव में bidirectionals के लिए एक उपयोगी जांच के होते हैं। हालांकि एक

if (__first == __last) this_partitioning_is_done = true; 

का एक सरल शर्त के साथ पिछले विभाजन यात्रा (दाएं से बाएं/दाएं से बाएं से) में एक चेक के साथ इस को बदलने के लिए सक्षम होना चाहिए यह संभव quicksort लागू करने के लिए काफी कुशलता से केवल द्विदिश iterators का उपयोग कर है ? रिकर्सिव गहराई अभी भी संरक्षित की जा सकती है।

एनबी। मैंने अभी तक एक वास्तविक कार्यान्वयन का प्रयास नहीं किया है।

Answer 1

tl; डॉ: हाँ

आप कहते हैं के रूप में, समस्या, धुरी तत्व है, जो बीच में तत्व है खोजने के लिए रैंडम एक्सेस के साथ इस खोजने है हे (1) लेता है, के साथ इसे पाने के बिडरेक्शनल इटरेटर्स ओ (एन) (एन/2 ऑपरेशंस, सटीक होने के लिए) लेता है। हालांकि, प्रत्येक चरण में आपको उप कंटेनरों को बनाना होगा, बाएं और दाएं क्रमशः छोटे और बड़े नंबर होते हैं। यह वह जगह है जहां त्वरित प्रकार का मुख्य कार्य होता है, है ना?

अब, जब उप कंटेनर (रिकर्सन चरण के लिए) का निर्माण करते हैं तो मेरा दृष्टिकोण एक प्रतिरक्षक h अपने संबंधित फ्रंट तत्व को इंगित करना होगा।अब जब भी आप उप कंटेनर पर जाने के लिए अगला तत्व चुनते हैं, तो बस हर बार h अग्रिम करें। एक बार जब आप नए रिकर्सन चरण में उतरने के लिए तैयार हो जाते हैं तो इसमें h पिवट तत्व को इंगित किया जाएगा।

आपको केवल पहले पिवट को ढूंढना है जो वास्तव में कोई फर्क नहीं पड़ता, क्योंकि ओ (एन लॉग एन + एन/2) = ओ (एन लॉग एन)।

वास्तव में यह केवल एक रनटाइम ऑप्टिमाइज़ेशन है, लेकिन जटिलता पर इसका कोई प्रभाव नहीं पड़ता है, क्योंकि क्या आप एक बार सूची में फिर से भरते हैं (संबंधित उप कंटेनर में प्रत्येक मान डालने के लिए) या दो बार (पिवट खोजने के लिए और फिर प्रत्येक को रखें संबंधित उप कंटेनर में मूल्य) सभी समान हैं: ओ (2 एन) = ओ (एन)।
यह केवल निष्पादन समय (जटिलता नहीं) का सवाल है।

Answer 2

आपको यादृच्छिक अभिगम इटरेटर्स की आवश्यकता है क्योंकि आप आमतौर पर सूची के मध्य से पिवट तत्व चुनना चाहते हैं। यदि आप पिवोट के रूप में पहला या अंतिम तत्व चुनते हैं, तो बिडरेक्शनल इटरेटर्स पर्याप्त हैं, लेकिन फिर क्विक्सोर्ट पूर्व-क्रमबद्ध सूचियों के लिए ओ (एन^2) में गिरावट करता है।

Answer 3

दोगुनी-लिंक्ड सूची पर त्वरित-प्रकार की रणनीति को लागू करने में बिल्कुल कोई समस्या नहीं है। (मुझे लगता है कि इसे आसानी से एक सिंगल-लिंक्ड सूची में भी अनुकूलित किया जा सकता है)। परंपरागत त्वरित-प्रकार एल्गोरिदम में एकमात्र जगह जो यादृच्छिक-पहुंच आवश्यकता पर निर्भर करती है वह सेटअप चरण है जो पिवट तत्व का चयन करने के लिए कुछ "मुश्किल" का उपयोग करता है। हकीकत में ये सभी "चालें" केवल ह्यूरिस्टिक्स से ज्यादा कुछ नहीं हैं जिन्हें बहुत अधिक प्रभावी अनुक्रमिक तरीकों से प्रतिस्थापित किया जा सकता है।

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

पीएस हालांकि, मैं कहूंगा कि लिंक्ड सूचियों के लिए मर्ज-सॉर्ट एल्गोरिदम का परिणाम काफी अधिक सुरुचिपूर्ण कार्यान्वयन में होता है, जिसमें समान रूप से अच्छा प्रदर्शन होता है (जब तक कि आप कुछ मामलों से निपट नहीं रहे हैं जो विशेष रूप से त्वरित-क्रम के साथ बेहतर प्रदर्शन करते हैं)।