algorithm क्यों ढेर प्रकार का उपयोग हमेशा नहीं




sorting heapsort (4)

हीप सॉर्ट में O(n log(n)) सबसे खराब स्थिति जटिलता है। फिर भी अनुभवजन्य अध्ययन से पता चलता है कि आम तौर पर त्वरित सॉर्ट (और अन्य सॉर्टिंग एल्गोरिदम) ढेर प्रकार की तुलना में काफी तेज है, हालांकि इसकी सबसे खराब स्थिति जटिलता O(n²) : http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort3.html

इसके अलावा, विकिपीडिया पर त्वरित क्रम लेख से:

क्विकॉर्ट का सबसे प्रत्यक्ष प्रतियोगी हेपॉर्ट है। हेप्सपोर्ट का सबसे खराब केस चलने का समय हमेशा ओ (एन लॉग एन) होता है। लेकिन, हेपसॉर्ट औसत जगह पर क्विकॉर्ट की तुलना में औसतन थोड़ा धीमा माना जाता है। यह अभी भी बहस और अनुसंधान में है, कुछ प्रकाशनों के विपरीत यह दर्शाता है। [13] [14] Introsort Quicksort का एक रूप है जो हेडसेट पर स्विच करता है जब एक खराब मामला पता चला है कि QuickSort के सबसे खराब मामले चलने वाले समय से बचने के लिए। यदि यह पहले से ज्ञात है कि हेपसॉर्ट आवश्यक होने जा रहा है, तो इसका उपयोग सीधे घुसपैठ करने के लिए घुसपैठ के इंतजार से तेज होगा।

हालांकि, त्वरित क्रमों का उपयोग उन अनुप्रयोगों में कभी नहीं किया जाना चाहिए जिनके लिए प्रतिक्रिया समय की गारंटी की आवश्यकता होती है!

स्टैक ओवरफ्लो पर स्रोत: क्विक्सोर्ट बनाम हेपसोर्ट

इस प्रश्न का उत्तर यहां दिया गया है:

हीप सॉर्ट सॉर्टिंग एल्गोरिदम में ओ (nlogn) की सबसे खराब केस जटिलता प्रतीत होती है, और सॉर्टिंग ऑपरेशन के लिए ओ (1) स्पेस का उपयोग करती है।

यह सबसे क्रमबद्ध एल्गोरिदम से बेहतर लगता है। फिर, कोई भी एक सॉर्टिंग एल्गोरिदम के रूप में हमेशा हेप सॉर्ट का उपयोग क्यों नहीं करेगा (और लोग मर्ज सॉर्ट या त्वरित सॉर्ट जैसे सॉर्टिंग तंत्र का उपयोग क्यों करते हैं)?

साथ ही, मैंने लोगों को हेप सॉर्ट के साथ 'अस्थिरता' शब्द का उपयोग किया है। इसका क्या अर्थ है?


कोई रजत बुलेट नहीं है ...

बस एक और तर्क का जिक्र करने के लिए मैंने अभी तक नहीं देखा है:

यदि आपका डेटासेट वास्तव में बड़ा है और स्मृति में फिट नहीं है, तो एक आकर्षण की तरह सॉर्ट कामों को मर्ज करें। यह अक्सर क्लस्टर में उपयोग किया जाता है जहां डेटासेट सैकड़ों मशीनों पर फैल सकता है।


स्थिर सॉर्टिंग एल्गोरिदम समान कुंजी के साथ रिकॉर्ड के सापेक्ष क्रम को बनाए रखते हैं

कुछ अनुप्रयोगों को इस तरह की स्थिरता रखने की तरह, अधिकांश परवाह नहीं है, उदाहरण के लिए Google आपका मित्र है।

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

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


जब मैंने 80 के दशक के मध्य में टंडेम गैर-स्टॉप कंप्यूटर पर थोड़े समय के लिए काम किया, तो मैंने नोट किया कि सिस्टम इन-कोर सॉर्ट रूटीन हीपॉर्ट था, ठीक है क्योंकि उसने गारंटीकृत एनएलओएनएन प्रदर्शन दिया था। मैं किसी ऐसे व्यक्ति के बारे में नहीं जानता जिसके पास इसका उपयोग करने का कोई कारण था, हालांकि, मुझे नहीं पता कि यह अभ्यास में कैसे काम करता है। मुझे हेपसोर्ट पसंद है, लेकिन साथ ही साथ ऊपर बताई गई कमियों में मैंने सुना है कि यह आधुनिक यादों का खराब उपयोग करता है, क्योंकि यह स्मृति को पूरे स्थान पर एक्सेस करता है, जबकि क्विकॉर्ट और यहां तक ​​कि छोटे रेडिक्स प्रकार अपेक्षाकृत कम संख्या में अंतरण करते हैं अनुक्रमिक पढ़ने और लिखने की धाराओं के - तो कैश अधिक प्रभावी होते हैं।





heapsort