एक औसत चयन एल्गोरिदम को समझना?

Question

मैं वर्तमान में अपने खाली समय में एल्गोरिदम सीख रहा हूं लेकिन अध्याय 3 का चयन करते समय निम्नलिखित प्रश्न पूछें() एल्गोरिदम।

मैं समझता हूं कि मैं औसत संख्या (एन/2 वें सबसे छोटी संख्या) को खोजने के लिए चयन() एल्गोरिदम का उपयोग कर सकता हूं यदि मैं ए से एन संख्याओं से सरणी का उपयोग कर रहा था।

1) लेकिन यह थोड़ा सा है जिसे मैं समझने के लिए संघर्ष कर रहा हूं। ए = [3, 7, 5, 1, 4, 2, 6, 2]। मान लीजिए कि सरणी है। विभाजन() को प्रत्येक कॉल के बाद सरणी की सामग्री क्या है, और चयन() के प्रत्येक रिकर्सिव कॉल में पैरामीटर।

क्या कोई यह समझा सकता है कि वे इसे कैसे काम कर रहे हैं?

नीचे 2 एल्गोरिदम के लिए छद्म कोड है।

Select(A, p, r, k) { 
    /* return k-th smallest number in A[p..r] */ 
    if (p==r) return A[p] /* base case */ 
    q := Partition(A,p,r) 
    len := q – p + 1 
    if (k == len) return A[q] 
    else if (k<len) return Select(A,p,q-1,k) 
    else return Select(A,q+1,r,k-len) 
} 

और दूसरा कोड

Partition(A, p, r) { /* partition A[p..r] */ 
    x := A[r] /* pivot */ 
    i := p-1 
    for j := p to r-1 { 
     if (A[j] <= x) { 
      i++ 
      swap(A[i], A[j]) 
     } 
    } 
    swap(A[i+1], A[r]) 
    return i+1 
} 

है किताब मैं उपयोग कर रहा हूँ कहा जाता है ऐनी Kaldewaij द्वारा एल्गोरिदम की व्युत्पत्ति।

Answer 1

यह एल्गोरिदम दो चरणों में काम करता है। विभाजन कदम कुछ पिवट तत्व चुनकर काम करता है, फिर सरणी के तत्वों को पुन: व्यवस्थित करता है जैसे कि पिवट से कम सबकुछ एक तरफ होता है, पिवट की तुलना में सबकुछ दूसरी तरफ होता है, और पिवट सही जगह पर होती है। उदाहरण के लिए, सरणी

3 2 5 1 4 

दिया अगर हम 3 के एक धुरी लेने, तो हम इस तरह सरणी विभाजन हो सकता है:

2 1 3 5 4 
+--+^+--+ 
^ | ^
| | +--- Elements greater than 3 
| +-------- 3, in the right place 
+------------- Elements less than 3 

सूचना है कि हम सरणी हल नहीं है; हमने इसे हल करने के करीब बना दिया है। यह आकस्मिक रूप से, quicksort में पहला कदम है।

एल्गोरिदम फिर निम्न तर्क का उपयोग करता है। मान लीजिए कि हम उस तत्व को ढूंढना चाहते हैं जो क्रमबद्ध क्रम में इंडेक्स के से संबंधित है (kth सबसे छोटा तत्व)। फिर, हमने उठाए गए पिवट के संबंध में, तीन विकल्प हैं:

1. पिवट स्थिति स्थिति में है। फिर, चूंकि पिवट सही जगह पर है, इसलिए जो मूल्य हम खोज रहे हैं वह पिवट होना चाहिए। हो गया था।
2. पिवट के से अधिक स्थिति में है। तब kth सबसे छोटा तत्व पिवट से पहले सरणी के हिस्से में होना चाहिए, इसलिए हम kth सबसे छोटे तत्व के लिए सरणी के उस भाग को फिर से खोज सकते हैं।
3. पिवट के से छोटे स्थान पर है। फिर kth सबसे छोटा तत्व सरणी के ऊपरी क्षेत्र में कहीं होना चाहिए, और हम वहां पर भर्ती कर सकते हैं।

हमारे मामले में, मान लें कि हम दूसरे सबसे छोटे तत्व (स्थिति 2 पर एक) चाहते हैं। के बाद से धुरी स्थिति 3 पर समाप्त हो गया, इसका मतलब है कि दूसरी सबसे छोटा तत्व सरणी की पहली छमाही में कहीं होना चाहिए, इसलिए हम subarray

2 1 

पर recurse अगर हम वास्तविक मंझला तत्व चाहते थे होता है, चूंकि पिवट सरणी के बीच में टूट गया, हम केवल आउटपुट करेंगे कि औसत 3 है और किया जाना चाहिए।

अंत में, यदि हम चौथी सबसे छोटा तत्व की तरह कुछ चाहता था, तब से धुरी स्थिति 4 से पहले है, हम सरणी के ऊपरी हिस्से पर

5 4 

recurse होगा, अर्थात् और के लिए विचार करेंगे यहां पहला सबसे छोटा तत्व है, क्योंकि इस क्षेत्र से पहले तीन तत्व हैं।

शेष एल्गोरिदम विभाजन विभाजन (जो शायद एल्गोरिदम का सबसे अधिक हिस्सा है) और कैसे दोबारा पसंद करने के बारे में जानकारी है कि कैसे रिकर्स करना है या नहीं (थोड़ा कम मुश्किल)। उम्मीद है कि, हालांकि, यह उच्च स्तरीय संरचना एल्गोरिदम को अधिक समझ में मदद करती है।

आशा है कि इससे मदद मिलती है!