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




sorting heapsort (4)

एक स्थिर प्रकार एक ही कुंजी वाले आइटम के सापेक्ष क्रम को बनाए रखता है। उदाहरण के लिए, कल्पना करें कि आपके डेटा सेट में कर्मचारी आईडी और नाम के साथ रिकॉर्ड हैं। प्रारंभिक क्रम है:

1, Jim
2, George
3, Jim
4, Sally
5, George

आप नाम से सॉर्ट करना चाहते हैं। एक स्थिर प्रकार इस क्रम में वस्तुओं की व्यवस्था करेगा:

2, George
5, George
1, Jim
3, Jim
4, Sally

ध्यान दें कि "जॉर्ज" के लिए डुप्लिकेट रिकॉर्ड समान सापेक्ष क्रम में हैं क्योंकि वे प्रारंभिक सूची में थे। दो "जिम" रिकॉर्ड के साथ ही।

एक अस्थिर प्रकार इस तरह की वस्तुओं की व्यवस्था कर सकता है:

5, George
2, George
1, Jim
3, Jim
4, Sally

हेपसोर्ट स्थिर नहीं है क्योंकि ढेर पर संचालन बराबर वस्तुओं के सापेक्ष क्रम को बदल सकता है। सभी Quicksort कार्यान्वयन स्थिर नहीं हैं। यह इस बात पर निर्भर करता है कि आप विभाजन को कैसे कार्यान्वित करते हैं।

हालांकि हेपसोर्ट में O(n log(n)) सबसे बुरी स्थिति जटिलता है, जो पूरी कहानी नहीं बताती है। वास्तविक दुनिया के कार्यान्वयन में, निरंतर कारक हैं जो सैद्धांतिक विश्लेषण को ध्यान में नहीं रखता है। हेपसोर्ट बनाम क्विक्सोर्ट के मामले में, यह पता चला है कि क्विक्सोर्ट के सबसे बुरे मामलों को वास्तव में बहुत दुर्लभ बनाने के लिए तरीके हैं (उदाहरण के लिए 5 का औसत)। इसके अलावा, एक ढेर को बनाए रखना मुफ़्त नहीं है।

सामान्य वितरण के साथ एक सरणी को देखते हुए, क्विक्सोर्ट और हेपसोर्ट दोनों O(n log(n)) में चलेंगे। लेकिन क्विक्सोर्ट तेजी से निष्पादित करेगा क्योंकि इसके निरंतर कारक हेपसॉर्ट के निरंतर कारकों से छोटे होते हैं। इसे सरलता से रखने के लिए, ढेर को बनाए रखने से विभाजन तेजी से होता है।

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

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

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

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


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

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

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


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

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

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

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


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

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

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

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

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







heapsort