मर्जिसोर्ट को सूचियों को सॉर्ट करते समय "जाने का तरीका" क्यों माना जाता है और क्विकॉर्ट नहीं? मैंने इसे एक व्याख्यान में सुना है जिसे मैंने ऑनलाइन देखा, और इसे दो वेबसाइटों में देखा।विलय सूचियों के लिए विलय बेहतर क्यों है?
क्विक्सॉर्ट में दक्षता के मुख्य स्रोतों में से एक locality of reference है, जहां कंप्यूटर हार्डवेयर अनुकूलित किया गया है ताकि स्मृति के स्थान पर पहुंचने वाले स्मृति स्थानों तक पहुंचने से स्मृति में बिखरे हुए स्मृति स्थानों तक पहुंचने से तेज़ हो। क्विकॉर्ट में विभाजन चरण में आमतौर पर उत्कृष्ट इलाके होता है, क्योंकि यह आगे और पीछे के पास लगातार सरणी तत्वों तक पहुंचता है। नतीजतन, क्विकॉर्ट्स अन्य सॉर्टिंग एल्गोरिदम की तुलना में बहुत बेहतर प्रदर्शन करता है जैसे कि हेपसोर्ट, हालांकि यह अक्सर तुलनात्मक रूप से समान संख्या और स्वैप करता है, क्योंकि हेपसोर्ट के मामले में पहुंच अधिक बिखरी हुई है।
इसके अतिरिक्त, क्विकॉर्ट आमतौर पर अन्य सॉर्टिंग एल्गोरिदम की तुलना में बहुत तेज है क्योंकि यह अस्थायी मूल्यों को रखने के लिए किसी भी सहायक सरणी बनाने की आवश्यकता के बिना, जगह में संचालित होता है। मर्ज सॉर्ट की तरह कुछ की तुलना में, यह एक बड़ा फायदा हो सकता है क्योंकि सहायक सरणी आवंटित करने और रद्द करने के लिए आवश्यक समय ध्यान देने योग्य हो सकता है। ऑपरेटिंग इन-प्लेस भी क्विकॉर्ट के इलाके में सुधार करता है।
लिंक की गई सूचियों के साथ काम करते समय, इनमें से कोई भी लाभ आवश्यक रूप से लागू नहीं होता है। चूंकि लिंक की गई सूची कोशिकाओं को अक्सर स्मृति में बिखराया जाता है, इसलिए आसन्न लिंक्ड सूची कक्षों तक पहुंचने के लिए कोई इलाके बोनस नहीं होता है। नतीजतन, Quicksort के विशाल प्रदर्शन फायदे में से एक खाया जाता है। इसी तरह, काम करने के लाभ अब लागू नहीं होते हैं, क्योंकि सॉर्ट की लिंक्ड सूची एल्गोरिदम को मर्ज करने के लिए किसी भी अतिरिक्त सहायक स्टोरेज स्पेस की आवश्यकता नहीं होती है।
उस ने कहा, क्विकॉर्ट अभी भी लिंक्ड सूचियों पर बहुत तेज है। मर्ज सॉर्ट बस तेज़ हो जाता है क्योंकि यह सूचियों को आधा में समान रूप से विभाजित करता है और विभाजन चरण को करने के बजाय विलय करने के लिए प्रति पुनरावृत्ति कम काम करता है।
आशा है कि इससे मदद मिलती है!
तीसरे पैराग्राफ की आखिरी पंक्ति में आपने लिखा "इसी प्रकार, काम करने के लाभ अब लागू नहीं होते हैं, क्योंकि मर्ज सॉर्ट की लिंक्ड सूची एल्गोरिदम को किसी भी अतिरिक्त सहायक स्टोरेज स्पेस की आवश्यकता नहीं होती है।" उसे सहायक स्टोरेज स्पेस की आवश्यकता क्यों नहीं है? – Geek
@ गीक मुझे शायद यह कहना चाहिए था कि "मर्ज सॉर्ट की लिंक्ड लिस्ट एल्गोरिदम की आवश्यकता नहीं है ** ओ (एन) ** सहायक स्टोरेज स्पेस।" मानक सरणी-आधारित विलय एल्गोरिदम के लिए आवश्यक है कि आप मर्ज करने के दौरान अतिरिक्त संग्रहण स्थान आवंटित करें क्योंकि तत्वों को चारों ओर स्थानांतरित करने की आवश्यकता है। लिंक्ड सूचियों के साथ मर्ज सॉर्ट में, उन्हें आसानी से रिंक करके बाहरी सरणी आवंटित किए बिना तत्वों को स्थानांतरित करना संभव है। – templatetypedef
खोजने की लागत() विलय से त्वरित रूप से अधिक हानिकारक है।
मर्ज सॉर्ट डेटा पर अधिक "शॉर्ट रेंज" संचालन करता है, जो इसे लिंक्ड सूचियों के लिए अधिक उपयुक्त बनाता है, जबकि क्विक्सॉर्ट यादृच्छिक पहुंच डेटा संरचना के साथ बेहतर काम करता है।
'ढूंढें() 'से आपका क्या मतलब है? – templatetypedef
डेटा संरचना में प्रविष्टियों की तलाश। एक लिंक्ड लिंस्ट के लिए आप हमेशा एक टेप खेलने की तरह आगे बढ़ रहे/रिवाइंडिंग कर रहे हैं। –
आपको लिंक किए गए सूची मामले में क्विकॉर्ट के लिए सरणी पर उपयोग किए गए यादृच्छिक-पहुंच विभाजन फ़ंक्शन का उपयोग करने की आवश्यकता नहीं है। आप सूची में पुनरावृत्त करके लिंक्ड सूची को विभाजित कर सकते हैं और प्रत्येक तत्व को तीन सूचियों में से एक में वितरित कर सकते हैं - एक "कम से कम" सूची, एक "अधिक से अधिक" सूची, और "बराबर सूची", फिर बाद वाले दो पर पुनरावर्ती। आप सही हैं कि मानक विभाजन धीमा है, लेकिन यह मूल रूप से लिंक की गई सूची quicksort धीमी नहीं है। – templatetypedef
इसे देखें http://stackoverflow.com/questions/497794/quicksort-slower-than-mergesort –