java sort हेपसॉर्ट की सहज ज्ञान युक्त समझ?




quick sort (6)

स्कूल में हम वर्तमान में जावा में सॉर्टिंग एल्गोरिदम सीख रहे हैं और मुझे अपने होमवर्क हेप सॉर्ट के लिए मिला है। मैंने अपनी पढ़ाई की, मैंने जितना संभव हो उतना पता लगाने की कोशिश की, लेकिन ऐसा लगता है कि मैं अवधारणा को समझ नहीं सकता।

मैं आपको जावा प्रोग्राम लिखने के लिए नहीं कह रहा हूं, अगर आप मुझे बस इतना ही समझा सकते हैं कि आप हीप सॉर्ट कैसे काम कर सकते हैं।


मुझे अपने एल्गोरिदम विश्लेषण प्रोफेसर को याद रखने के लिए याद है कि ढेर प्रकार एल्गोरिदम बजरी के ढेर की तरह काम करता है:

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

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

हेड सॉर्ट कैसे काम करता है यह समझाने के लिए यह सरल तरीका है कि मैं सरल या सरल तरीका जानता हूं।


हीप सॉर्ट में समय जटिलता ओ (nlogn) और अंतरिक्ष जटिलता ओ (1) के साथ सरल तर्क शामिल हैं

 public class HeapSort {

public static void main(String[] args) {
     Integer [] a={12,32,33,8,54,34,35,26,43,88,45};

     HeapS(a,a.length-1);

    System.out.println(Arrays.asList(a));

}

private static void HeapS(Integer[] a, int l) {


    if(l<=0)
        return;

    for (int i = l/2-1; i >=0 ; i--) {

        int index=a[2*i+1]>a[2*i+2]?2*i+1:2*i+2;
        if(a[index]>a[i]){
            int temp=a[index];
            a[index]=a[i];
            a[i]=temp;
        }

    }
    int temp=a[l];
    a[l]=a[0];
    a[0]=temp;

    HeapS(a,l-1);

  }
}

मैं देखूंगा कि मैं इसका जवाब देने में कैसे जाता हूं, क्योंकि ढेर के प्रकार के लिए मेरी व्याख्या और ढेर क्या होगा ...

... ओह, भयानक

वैसे भी, सबसे पहले, हम बेहतर जांच करेंगे कि एक ढेर क्या है:

Wikipedia से लिया गया Wikipedia , एक ढेर है:

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

बहुत अधिक, एक ढेर एक बाइनरी पेड़ है जैसे किसी भी नोड के सभी बच्चे उस नोड से छोटे होते हैं।

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

यह एल्गोरिदम ओ ( एन एलजी (एन) क्यों है? चूंकि एक ढेर पर सभी संचालन ओ ( एलजी (एन) ) हैं और नतीजतन, आप एन ऑपरेशंस करेंगे, जिसके परिणामस्वरूप ओ ( एन एलजी (एन) ) का कुल चलने वाला समय होगा।

मुझे आशा है कि मेरे भयानक रान ने आपकी मदद की! यह थोड़ा सा शब्द है; उसके लिए माफ़ करना...


ठीक है, तो मूल रूप से आप एक ढेर लेते हैं और ढेर में पहला नोड खींचते हैं - क्योंकि पहले नोड को क्रम की दिशा के आधार पर सबसे बड़ा / छोटा होने की गारंटी दी जाती है। मुश्किल चीज पहले स्थान पर ढेर को फिर से संतुलित / बना रही है।

ढेर की प्रक्रिया को समझने के लिए मेरे लिए दो कदम उठाने की आवश्यकता थी - सबसे पहले यह एक पेड़ के रूप में सोचने, मेरे सिर को इसके चारों ओर ले जाने के बाद, उस पेड़ को सरणी में बदलना ताकि यह उपयोगी हो सके।

इसका दूसरा भाग अनिवार्य रूप से पेड़ की चौड़ाई को पार करना है, प्रत्येक तत्व को सरणी में जोड़ने के लिए बाएं से बाएं। तो निम्नलिखित पेड़:

                                    73                          
                                 7      12          
                               2   4  9   10    
                             1          

{73,7,12,2,4,9,10,1} होगा

पहले भाग को दो चरणों की आवश्यकता है:

  1. सुनिश्चित करें कि प्रत्येक नोड में दो बच्चे हैं (जब तक आपके पास उपरोक्त पेड़ में ऐसा करने के लिए पर्याप्त नोड्स न हों।
  2. सुनिश्चित करें कि प्रत्येक नोड बड़ा है (या छोटे से छंटनी अगर छोटे हो) अपने बच्चों की तुलना में।

इसलिए संख्याओं की एक सूची को अपनाने के लिए आप प्रत्येक को ढेर में जोड़ते हैं, फिर क्रमशः उन दो चरणों का पालन करते हैं।

ऊपर अपना ढेर बनाने के लिए मैं पहले 10 जोड़ दूंगा - यह एकमात्र नोड है इसलिए ऐसा करने के लिए कुछ भी नहीं है। बाईं ओर के बच्चे के रूप में 12 जोड़ें:

    10
  12

यह 1 को संतुष्ट करता है, लेकिन 2 नहीं, इसलिए मैं उन्हें गोल कर दूंगा:

    12
  10

7 जोड़ें - करने के लिए कुछ भी नहीं

    12
  10  7

73 जोड़ें

          12
       10     7
    73

10 <73 इसलिए उन्हें स्वैप करने की आवश्यकता है:

          12
       73     7
    10

12 <73 इसलिए उन्हें स्वैप करने की आवश्यकता है:

          73
       12     7
    10

2 जोड़ें - करने के लिए कुछ नहीं

          73
       12     7
    10   2

4 जोड़ें - करने के लिए कुछ भी नहीं

          73
       12     7
    10   2  4

9 जोड़ें

          73
       12     7
    10   2  4   9

7 <9 - स्वैप

          73
       12     9
    10   2  4   7

1 जोड़ें - करने के लिए कुछ नहीं

          73
       12     9
    10   2  4   7
  1

हमारे पास ढेर है: डी

अब आप प्रत्येक तत्व को शीर्ष से हटा दें, हर बार पेड़ के शीर्ष पर अंतिम तत्व में स्वैपिंग करें, फिर पेड़ को फिर से संतुलित करें:

73 रन लें - अपनी जगह पर 1 डालें

          1
       12     9
    10   2  4   7

1 <12 - तो उन्हें स्वैप करें

          12
        1    9
    10   2  4   7

1 <10 - तो उन्हें स्वैप करें

          12
       10     9
     1   2  4   7

12 बंद करें - 7 के साथ प्रतिस्थापित करें

          7
       10     9
     1   2  4   

7 <10 - उन्हें स्वैप करें

          10
       7     9
     1   2  4   

10 बंद करें - 4 के साथ प्रतिस्थापित करें

          4
       7     9
    1   2  

4 <7 - स्वैप

          7
       4     9
    1   2  

7 <9 - स्वैप

          9
       4     7
    1   2 

9 बंद करें - 2 के साथ प्रतिस्थापित करें

          2
       4     7
    1   

2 <4 - उन्हें स्वैप करें

          4
       2     7
    1  

4 <7 - उन्हें स्वैप करें

          7
       2     4
    1  

7 बंद करें - 1 के साथ प्रतिस्थापित करें

          1
       2     4

1 <4 - उन्हें स्वैप करें

          4
       2     1

4 ले लो - 1 के साथ प्रतिस्थापित करें

          1
       2

1 <2 - उन्हें स्वैप करें

          2
       1

2 ले लो - 1 के साथ प्रतिस्थापित करें

          1

1 ले लो

क्रमबद्ध सूची voila।


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

सहजता से, ढेर प्रकार एक विशेष डेटा संरचना का निर्माण करके काम करता है जिसे बाइनरी हीप कहा जाता है जो अनदेखा सरणी तत्वों से सबसे बड़ा तत्व ढूंढने की गति करता है। बाइनरी ढेर निम्नलिखित परिचालनों का समर्थन करते हैं:

  • सम्मिलित करें , जो ढेर में तत्व डालता है, और
  • हटाएं-मैक्स , जो ढेर के सबसे बड़े तत्व को हटा देता है और देता है।

बहुत उच्च स्तर पर, एल्गोरिदम निम्नानुसार कार्य करता है:

  • सरणी के प्रत्येक तत्व को एक नए बाइनरी ढेर में डालें
  • I = n नीचे 1 तक:
    • ढेर पर सबसे बड़ा तत्व प्राप्त करने के लिए ढेर पर हटाएं-अधिकतम कॉल करें
    • इस तत्व को स्थिति में लिखें I।

यह सरणी को टाइप करता है क्योंकि हटाएं-मैक्स द्वारा लौटाए गए तत्व अवरोही क्रम में हैं। एक बार सभी तत्वों को हटा दिए जाने के बाद, सरणी को क्रमबद्ध किया जाता है।

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

आम तौर पर, ढेर क्रम दो प्रमुख अनुकूलन कार्यरत है। सबसे पहले, हीप को आम तौर पर ढेर के संपीड़ित प्रतिनिधित्व के रूप में सरणी के इलाज के द्वारा सरणी के अंदर जगह में बनाया जाता है। यदि आप एक हेपसोर्ट कार्यान्वयन को देखते हैं, तो आप आमतौर पर दो से गुणा करके और विभाजित करने के आधार पर सरणी सूचकांक के असामान्य उपयोग देखेंगे; ये काम का उपयोग करते हैं क्योंकि वे सरणी को एक संघीय डेटा संरचना के रूप में देख रहे हैं। नतीजतन, एल्गोरिदम केवल ओ (1) सहायक भंडारण स्थान की आवश्यकता है।

दूसरा, ढेर को एक समय में एक तत्व बनाने के बजाय, ढेर आमतौर पर एक विशेष एल्गोरिदम का उपयोग करके बनाया जाता है जो समय में ढेर बनाने के लिए Θ (एन) में चलता है। दिलचस्प बात यह है कि, कुछ मामलों में यह कोड को पढ़ने में आसान बनाता है क्योंकि कोड का पुन: उपयोग किया जा सकता है, लेकिन एल्गोरिदम स्वयं समझने और विश्लेषण करने के लिए थोड़ा सा कठिन हो जाता है।

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

एक बार जब आप हेपसोर्ट की बेहतर समझ लेते हैं, तो आप introsort एल्गोरिदम में देखना चाह सकते हैं, जो कि त्वरित तेज़ सॉर्टिंग एल्गोरिदम उत्पन्न करने के लिए क्विकॉर्ट, हेपॉर्ट और सम्मिलन सॉर्ट को जोड़ता है जो क्विकॉर्ट (औसत पर तेज़ सॉर्टिंग), हेपसोर्ट की शक्ति को जोड़ता है ( उत्कृष्ट सबसे खराब केस व्यवहार), और सम्मिलन क्रम (छोटे सरणी के लिए तेज़ सॉर्टिंग)। इंट्रोसोर्ट का उपयोग सी ++ के एसडीडी std::sort फ़ंक्शन के कई कार्यान्वयन में किया जाता है, और एक बार आपके पास एक कार्यरत हेपसॉर्ट होने के बाद स्वयं को लागू करना बहुत कठिन नहीं होता है।

उम्मीद है की यह मदद करेगा!


मान लीजिए कि आपके पास एक विशेष डेटा संरचना है (जिसे ढेर कहा जाता है) जो आपको संख्याओं की एक सूची स्टोर करने की अनुमति देता है और आपको O(lg n) समय में सबसे छोटे को पुनर्प्राप्त करने और हटाने देता है।

क्या आप देखते हैं कि यह एक बहुत ही सरल सॉर्टिंग एल्गोरिदम की ओर जाता है?

कठिन हिस्सा (यह वास्तव में कठिन नहीं है) ढेर को लागू कर रहा है।





heapsort