त्वरित सॉर्ट एल्गोरिदम सुधार यदि अधिक डुप्लिकेट कुंजी

Question

मैं रॉबर्ट सेडविक एल्गोरिदम और डेटा संरचनाओं भाग 1-4 द्वारा पुस्तक में त्वरित क्रम एल्गोरिदम पढ़ रहा हूं।

template <class item> 

static void quicksort(item [] a, int l, int r) 
{ 
    if(r <= l) return; 
    int i = partition(a,l,r); 
    quicksort(a, l, i-1); 
    quicksort(a, i+1, r); 
} 

template <class item> 
int partition(item a[], int l, int r) 
{ 
    int i = l-1; j = r; item v = a[r]; 

    for(;;) { 
     while(a[++i] < v); 
     while(v < a[--j]) 
      if(j == l) 
       break; 
     if(i >= j) 
      break; // pointer crossing. 
     exch(a[i], a[j]); 
    } 

    exch(a[i], a[r]); 
    return i; 
} 

पुस्तक में उपरोक्त एल्गोरिदम पर निम्नलिखित पाठ है।

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

मेरे सवाल कर रहे हैं

1. हम कैसे नीचे दिए गए विवरण के साथ कार्यक्रम ऊपर संशोधित कर सकते हैं? मुझे पाठ को समझने के लिए इसे संशोधित करने में कठिनाई हो रही है।
2. अधिक डुप्लिकेट कुंजी मौजूद होने पर त्वरित प्रकार से ऊपर एल्गोरिदम प्रभावी ढंग से काम नहीं करता है।
3. यदि अधिक डुप्लिकेशन कुंजी मौजूद हैं तो संशोधन में सुधार कैसे किया जाता है?
4. लेखक का क्या अर्थ है "वह कॉल में पहला विभाजन त्वरित-क्रम (ए, आई + 1, आर) खराब हो जाता है, क्योंकि इसकी सही कुंजी सबसे छोटी है।" ? लेखक का अर्थ यहां खराब हो गया है?

अपना समय और मदद के लिए धन्यवाद।

Answer 1

>> त्वरित तरह एल्गोरिथ्म ऊपर क्यों प्रभावी ढंग से काम नहीं करता है तो अधिक डुप्लिकेट चाबी मौजूद हैं?

यह अक्षम हो जाता है क्योंकि अपने को तोड़ने शर्त है: if(i >= j) break;
हां, तो आप i और j के साथ दोनों पक्षों से स्कैन के रूप में, यह संभव है कि आप जब दे i से अधिक पार की मैं == जे बजाय तोड़ने j।

खराब संभवतः तब हो सकता है जब हम i==j पर तोड़ते हैं कई डुप्लिकेट कुंजी मौजूद हैं?

आप पहली बार से i==j; के लिए तोड़ जब जबकि पाश आप a[i] >= v था और किया जाना चाहिए दूसरा, जबकि लेकिन पाश a[j] <=v हम एक के लिए 'ब्रेक' विचार कर रहे हैं के बाद से से: i==j हां, तो a[i] = a[j] = v अर्थातa[i]v के समान है, आपके पिवट तत्व।

ऐसे परिदृश्य में, आपका बाहरी exch(a[i], a[r]); केवल पिवट मूल्य का आदान-प्रदान करेगा।
इसलिए, आपके अगले रिकर्सिव कॉल quicksort(a, i+1, r); में सरणी के दाएं भाग के लिए, आपके पास न्यूनतम अंत में बैठे न्यूनतम तत्व होंगे। (आपका पिवोट चुनने की रणनीति बस है, item v = a[r];) और हम सभी जानते हैं कि यह QuickSort के लिए चुनना बुरा है एक पिवट तत्व जो न्यूनतम या अधिकतम सरणी के बराबर होता है। इसलिए, आपके अर्धशतक के लिए बाद में रिकर्सिव कॉल एक खराब हो जाएगा।
यही कारण है कि लेखक i == j के लिए तोड़ने की सलाह नहीं दे रहा है लेकिन ऐसा होने से ठीक पहले उन्हें पकड़ें।

>> लेखक का मतलब यहां खराब हो गया है?

यहां कमजोर पड़ने का मतलब है, रिकर्सन पेड़ खराब हो रहा है यानी बाद की समस्याएं लगभग बराबर आकारों से उत्पन्न नहीं हो रही हैं। आप आकार आकार की समस्या को N-1 और 1 की तुलना में कुछ अधिक संतुलित के बजाय, N/2 और N/2 की समस्याओं में विभाजित करने की समस्या को हल कर रहे हैं।

>> हम नीचे दिए गए विवरण के साथ प्रोग्राम को कैसे संशोधित कर सकते हैं?

हम तो वह ऐसा लागू हो सकते हैं:

int partition(int A[], int l, int r){ 
     int i=l-1, j=r, v = A[r]; 
     for(;;){ 
       while(A[++i] < v); 
       while(A[--j] > v) 
         if(j == l) 
           break; 
       if(i>=j) 
         break; 
       swap(A[i], A[j]); 
     } 
     if(i == j){// case when we stopped at the pivot element. 
       j = j+1;//backtrack j 1 step. 
       if(j <= r) 
        swap(A[j], A[r]); 
       return j;// partition the subsequent problems around j now. 
     } 
     swap(A[i], A[r]); 
     return i; 
} 

>> कैसे संशोधन ऊपर अगर अधिक दोहराव कुंजी मौजूद नहीं है में सुधार?
यह आपको एक अपरिवर्तनीय मामले के स्पष्ट परिदृश्य उत्पन्न करने के द्वारा प्रदर्शन में सुधार करता है।