सैंपलसॉर्ट: Difference between revisions

Latest revision as of 13:52, 14 August 2023

सैंपलसॉर्ट, डिवाइड एंड कंकर एल्गोरिथ्म पर आधारित एक सॉर्टिंग एल्गोरिथ्म है, जिसका उपयोग प्रायः पैरलेल प्रोसेसिंग सिस्टम में किया जाता है।^[1] पारंपरिक डिवाइड एंड कंकर एल्गोरिथ्म, ऐरे को सब-इंटरवल या बकेट में विभाजित करता है। फिर इस बकेट को अलग-अलग क्रमबद्ध किया जाता है और एक साथ जोड़ दिया जाता है। यद्यपि, यदि ये ऐरे गैर-समान रूप से वितरित किए गए है, तो इन सॉर्टिंग एल्गोरिदम का प्रदर्शन अत्यधिक सीमा तक कम हो सकता है। सैंपलसॉर्ट इस समस्या का समाधान करने में सक्षम है जिसमें n-एलिमेंट सीक्वन्स के लिए एक s आकार का सैम्पल चुनकर तथा उस सैंपल को सॉर्ट करने के उपरांत p-1 < s एलेमेन्ट को परिणाम से चुनकर बकेट की रेंज निर्धारित की जाती है। ये एलमेंट (जिन्हें स्प्लिटर्स कहा जाता है) फिर ऐरे को लगभग $p$ समान बकेट में विभाजित करते हैं।^[2] सैंपलसॉर्ट का वर्णन 1970 के लेख, सैंपलसॉर्ट: ए सैंपलिंग अप्रोच टू मिनिमल स्टोरेज ट्री सॉर्टिंग में डब्ल्यू. डी. फ्रेज़र और ए. सी. मैककेलर द्वारा किया गया है।^[3]

एल्गोरिथम

सैम्पल सॉर्ट क्विक सॉर्ट का सामान्यीकरण है। जहां क्विक सॉर्ट प्रत्येक चरण में अपने इनपुट को पिवट नामक एकल मान के आधार पर दो भागों में विभाजित करता है, सैंपलसॉर्ट इसके अतिरिक्त अपने इनपुट से एक बड़ा सैम्पल लेता है और अपने डेटा को तदनुसार बकेट में विभाजित करता है। क्विकसॉर्ट की तरह, यह फिर बकेट को पुनरावर्ती रूप से सॉर्ट करता है।

सैंपलसॉर्ट कार्यान्वयन तैयार करने के लिए, हमें $p$ बकेट की संख्या तय करने की आवश्यकता होती है। जब यह किया जाता है, तो वास्तविक एल्गोरिदम तीन चरणों में संचालित होता है:^[4]

सैम्पल $p -1$ इनपुट से तत्व (स्प्लिटर्स)। सॉर्ट करें; आसन्न स्प्लिटर्स का प्रत्येक युग्म फिर एक बकेट को परिभाषित करता है।
डेटा लूप करें, प्रत्येक तत्व को उपयुक्त बकेट में रखें। (इसका तात्पर्य यह हो सकता है: इसे मल्टीप्रोसेसर सिस्टम में एक प्रोसेसर को भेजें।)
प्रत्येक बकेट को क्रमबद्ध करें.

पूर्ण क्रमबद्ध आउटपुट बकेट का संयोजन है।

एक सामान्य रणनीति है कि p को उपलब्ध प्रोसेसरों के संख्या के बराबर रखा जाता है। फिर डेटा प्रोसेसरों के बीच वितरित किया जाता है, जो कुछ अन्य, अनुक्रमशील, सॉर्टिंग एल्गोरिदम का उपयोग करके बकेटों को क्रमबद्ध करते हैं।

स्यूडोकोड

निम्नलिखित सूची उपर्युक्त तीन चरण वाले एल्गोरिदम को स्यूडोकोड के रूप में प्रदर्शित करती है और दिखाती है कि एल्गोरिदम सिद्धांत रूप में कैसे कार्य करता है।^[5] निम्नांकित में, $A$ अवर्गीकृत डेटा है, $k$ ओवरसैंपलिंग कारक है, जिस पर बाद में चर्चा की गई है, और $p$ स्प्लिटर्स की संख्या है.

function sampleSort(A[1..n],  $k$ ,  $p$ )
    // if average bucket size is below a threshold switch to e.g. quicksort
    if n / k < threshold then smallSort(A) 
    /* Step 1 */
    select S = [S₁, ..., S_(p−1)k] randomly from // select samples
    sort  $S$  // sort sample
    [s₀, s₁, ..., s_p−1, s_p] <- [-∞, S_k, S_2k, ..., S_(p−1)k, ∞] // select splitters
    /* Step 2 */
    for each a in A
        find  $j$  such that s_j−1 < a <= s_j
        place  $a$  in bucket b_j
    /* Step 3 and concatenation */
    return concatenate(sampleSort(b₁), ..., sampleSort(b_k))

स्यूडोकोड मूल फ्रेज़र और मैककेलर एल्गोरिदम से भिन्न है।^[3] स्यूडोकोड में, सैंपलसॉर्ट को पुनरावर्ती रूप से कार्यवान्वित किया जाता है। फ़्रेज़र और मैककेलर ने केवल एक बार सैंपलसॉर्ट को कार्यान्वित किया और निम्नलिखित सभी पुनरावृत्तियों में क्विकसॉर्ट का उपयोग किया।

कम्प्लेक्सिटी

$p$ प्रोसेसर समानांतर कार्यान्वयन के लिए बिग ओ अंकन में दी गई कम्प्लेक्सिटी:

स्प्लिटर्स खोजें.

O\left({\frac {n}{p}}+\log(p)\right)

बकेट को भेजें.

O

[1]

[2]

[3]

[4]

[5]

@@ Line 33: / Line 33: @@
 स्यूडोकोड मूल फ्रेज़र और मैककेलर एल्गोरिदम से भिन्न है।<ref name=Frazer70>{{cite journal | last1=Frazer|first1=W. D.| last2=McKellar|first2=A. C.| title=Samplesort: A Sampling Approach to Minimal Storage Tree Sorting| journal=Journal of the ACM| date=1970-07-01| volume=17| issue=3| pages=496–507| doi=10.1145/321592.321600| s2cid=16958223 }}</ref> स्यूडोकोड में, सैंपलसॉर्ट को पुनरावर्ती रूप से कार्यवान्वित किया जाता है। फ़्रेज़र और मैककेलर ने केवल एक बार सैंपलसॉर्ट को कार्यान्वित किया और निम्नलिखित सभी पुनरावृत्तियों में क्विकसॉर्ट का उपयोग किया।
-[[Category:All articles with unsourced statements]]
-[[Category:Articles with invalid date parameter in template]]
-[[Category:Articles with unsourced statements from January 2018]]
-[[Category:Collapse templates]]
-[[Category:Created On 26/07/2023]]
-[[Category:Machine Translated Page]]
-[[Category:Navigational boxes| ]]
-[[Category:Navigational boxes without horizontal lists]]
-[[Category:Pages with script errors]]
-[[Category:Sidebars with styles needing conversion]]
 === कम्प्लेक्सिटी ===
@@ Line 85: / Line 85: @@
 <math display="block">P_\text{fail} = n \cdot P(X < S) \le n \cdot \exp\left(\dfrac{-\epsilon^2 \cdot S}{2}\right) \le n \cdot \dfrac{1}{n^2} \text{ for } S \ge \dfrac{4}{\epsilon^2}\ln n</math>
-[[Category:All articles with unsourced statements]]
-[[Category:Articles with invalid date parameter in template]]
-[[Category:Articles with unsourced statements from January 2018]]
-[[Category:Collapse templates]]
-[[Category:Created On 26/07/2023]]
-[[Category:Machine Translated Page]]
-[[Category:Navigational boxes| ]]
-[[Category:Navigational boxes without horizontal lists]]
-[[Category:Pages with script errors]]
-[[Category:Sidebars with styles needing conversion]]
 == कई इडेंटिकल 'की'(key) ==
@@ Line 110: / Line 110: @@
 के दशक में [[कनेक्शन मशीन]] सुपरकंप्यूटर पर किए गए प्रयोग ने दिखाया कि सैंपलसॉर्ट बड़े डेटासेट को सॉर्ट करने में विशेष रूप से अच्छा है, क्योंकि इसका इंटरप्रोसेसर संचार ओवरहेड कम होता है।<ref>{{cite conference |title=A Comparison of Sorting Algorithms for the Connection Machine CM-2 |first1=Guy E. |last1=Blelloch |authorlink1=Guy Blelloch |first2=Charles E. |last2=Leiserson |authorlink2=Charles E. Leiserson |first3=Bruce M. |last3=Maggs |first4=C. Gregory |last4=Plaxton |first5=Stephen J. |last5=Smith |first6=Marco |last6=Zagha |conference=ACM Symp. on Parallel Algorithms and Architectures |year=1991 |url=https://www.cs.cmu.edu/~scandal/papers/cm-sort-SPAA91.html |citeseerx=10.1.1.131.1835}}</ref> हाल के [[GPGPU|GPUs]] पर, इस एल्गोरिदम का प्रयोग उसके विकल्पों की तुलना में कम प्रभावी हो सकता है।<ref>{{cite conference |first1=Nadathur |last1=Satish |first2=Mark |last2=Harris |first3=Michael |last3=Garland |title=Designing Efficient Sorting Algorithms for Manycore GPUs |conference=Proc. IEEE Int'l Parallel and Distributed Processing Symp. |citeseerx=10.1.1.190.9846}}</ref>
-[[Category:All articles with unsourced statements]]
-[[Category:Articles with invalid date parameter in template]]
-[[Category:Articles with unsourced statements from January 2018]]
-[[Category:Collapse templates]]
-[[Category:Created On 26/07/2023]]
-[[Category:Machine Translated Page]]
-[[Category:Navigational boxes| ]]
-[[Category:Navigational boxes without horizontal lists]]
-[[Category:Pages with script errors]]
-[[Category:Sidebars with styles needing conversion]]
 == सैम्पल सॉर्ट का एफीसिएंट कार्यान्वयन ==
-[[File:Animation.png|thumb|सुपर स्केलर सैंपलसॉर्ट का एनिमेटेड उदाहरण। प्रत्येक चरण में, जिन संख्याओं की तुलना की जाती है उन्हें नीले रंग से चिह्नित किया जाता है और जो संख्याएं अन्यथा पढ़ी या लिखी जाती हैं उन्हें लाल रंग से चिह्नित किया जाता है।]]जैसा कि ऊपर बताया गया है, सैंपलसॉर्ट एल्गोरिदम चयनित स्प्लिटर्स के अनुसार एलमेंट को विभाजित करता है। पेपर सुपर स्केलर सैंपल सॉर्ट में एक एफीसिएंट कार्यान्वयन रणनीति प्रस्तावित है।<ref name=":0"/>पेपर में प्रस्तावित कार्यान्वयन <math>n</math> एफीसिएंट कार्यान्वयन के लिए (इनपुट डेटा युक्त मूल ऐरे और एक अस्थायी) आकार की दो ऐरे का उपयोग करता है । इसलिए, कार्यान्वयन का यह संस्करण इन-प्लेस एल्गोरिदम नहीं है।
+[[File:Animation.png|thumb|सुपर स्केलर सैंपलसॉर्ट का एनिमेटेड उदाहरण। प्रत्येक चरण में, जिन संख्याओं की तुलना की जाती है उन्हें नीले रंग से चिह्नित किया जाता है और जो संख्याएं अन्यथा रीड या राइट कीजाती हैं उन्हें लाल रंग से चिह्नित किया जाता है।]]जैसा कि ऊपर बताया गया है, सैंपलसॉर्ट एल्गोरिदम चयनित स्प्लिटर्स के अनुसार एलमेंट को विभाजित करता है। पेपर सुपर स्केलर सैंपल सॉर्ट में एक एफीसिएंट कार्यान्वयन रणनीति प्रस्तावित है।<ref name=":0"/>पेपर में प्रस्तावित कार्यान्वयन <math>n</math> एफीसिएंट कार्यान्वयन के लिए (इनपुट डेटा युक्त मूल ऐरे और एक अस्थायी) आकार की दो ऐरे का उपयोग करता है । इसलिए, कार्यान्वयन का यह संस्करण इन-प्लेस एल्गोरिदम नहीं है।
 प्रत्येक रिकर्सन चरण में, डेटा को डिवाइड विधि से अन्य ऐरे में कॉपी किया जाता है। यदि डेटा अंतिम रिकर्सन चरण में अस्थायी ऐरे में है, तो डेटा को मूल ऐरे में वापस कॉपी किया जाता है।
@@ Line 138: / Line 138: @@
 बकेटों की संख्या {{mvar|k}} कंपाइल समय पर ज्ञात होती है, इसलिए कंपाइलर इस लूप को [[लूप अनरोलिंग|अनरोल कर]] सकता है। तुलना ऑपरेशन को [[प्रेडिकेशन (कंप्यूटर विज्ञान)|प्रेडिकेटेड इंस्ट्रक्शन्स]] के साथ लागू किया जाता है। इससे [[ब्रांच मिसप्रिडिक्शन]] नहीं होती है, जो तुलना ऑपरेशन को काफी धीमा बना सकता है।
-[[Category:All articles with unsourced statements]]
-[[Category:Articles with invalid date parameter in template]]
-[[Category:Articles with unsourced statements from January 2018]]
-[[Category:Collapse templates]]
-[[Category:Created On 26/07/2023]]
-[[Category:Machine Translated Page]]
-[[Category:Navigational boxes| ]]
-[[Category:Navigational boxes without horizontal lists]]
-[[Category:Pages with script errors]]
-[[Category:Sidebars with styles needing conversion]]
 === विभाजन ===
-एक प्रभावशील विभाजन के लिए, एल्गोरिदम को अग्रिम बकेटों का आकार जानने की जरूरत होती है। अनुक्रम के तत्वों को विभाजित करने और उन्हें एक एरे में रखने के लिए, हमें अग्रिम बकेटों के आकार को जानने की आवश्यकता होती है। एक साधारण एल्गोरिदम में हर बकेट के तत्वों की संख्या को गिन सकता है। फिर तत्वों को सही स्थान पर दूसरे एरे में डाला जा सकता है। इससे, हमें प्रत्येक तत्व के लिए दो बार बकेट का निर्धारण करने की आवश्यकता होगी (एक बार बकेट में तत्वों की संख्या को गिनने के लिए और एक बार उन्हें इन्सर्ट करने के लिए)।
+एक प्रभावशील विभाजन के लिए, एल्गोरिदम को अग्रिम बकेटों का आकार जानने की जरूरत होती है। अनुक्रम के एलमेंट को विभाजित करने और उन्हें एक एरे में रखने के लिए, हमें अग्रिम बकेटों के आकार को जानने की आवश्यकता होती है। एक साधारण एल्गोरिदम में हर बकेट के एलमेंट की संख्या को गिन सकता है। फिर एलमेंट को सही स्थान पर दूसरे एरे में डाला जा सकता है। इससे, हमें प्रत्येक तत्व के लिए दो बार बकेट का निर्धारण करने की आवश्यकता होगी (एक बार बकेट में एलमेंट की संख्या को गिनने के लिए और एक बार उन्हें इन्सर्ट करने के लिए)।
+इस दोहराने वाले तुलना को टालने के लिए, सुपर स्केलर सैंपल सॉर्ट एक अतिरिक्त एरे <math>o</math> (जिसे ऑरेकल कहा जाता है) का उपयोग करता है जो प्रत्येक तत्व के एक बकेट से सम्बंधित होता है। पहले, एल्गोरिदम <math>o</math> के संदर्भ को निर्धारित करके यह निर्धारित करता है, फिर बकेट का आकार निर्धारित करके एलमेंट को <math>o</math> द्वारा निर्धारित बकेट में रखता है। एरे <math>o</math> भी संग्रह स्थान में खर्च करता है, परंतु क्योंकि इसमें केवल <math>n\cdot \log k</math> बिट संभावित होते हैं, इन खर्चों को इनपुट एरे के अनुपात में छोटा माना जा सकता है।
-इस दोहराने वाले तुलना को टालने के लिए, सुपर स्केलर सैंपल सॉर्ट एक अतिरिक्त एरे <math>o</math> (जिसे ऑरेकल कहा जाता है) का उपयोग करता है जो प्रत्येक तत्व के एक बकेट से सम्बंधित होता है। पहले, एल्गोरिदम <math>o</math> के संदर्भ को निर्धारित करके यह निर्धारित करता है, फिर बकेट का आकार निर्धारित करके तत्वों को <math>o</math> द्वारा निर्धारित बकेट में रखता है। एरे <math>o</math> भी संग्रह स्थान में खर्च करता है, परंतु क्योंकि इसमें केवल <math>n\cdot \log k</math> बिट संभावित होते हैं, इन खर्चों को इनपुट एरे के अनुपात में छोटा माना जा सकता है।
-[[Category:All articles with unsourced statements]]
-[[Category:Articles with invalid date parameter in template]]
-[[Category:Articles with unsourced statements from January 2018]]
-[[Category:Collapse templates]]
-[[Category:Created On 26/07/2023]]
-[[Category:Machine Translated Page]]
-[[Category:Navigational boxes| ]]
-[[Category:Navigational boxes without horizontal lists]]
-[[Category:Pages with script errors]]
-[[Category:Sidebars with styles needing conversion]]
 == इन-प्लेस सैंपलसॉर्ट ==
@@ Line 177: / Line 177: @@
 === स्थानीय वर्गीकरण ===
-पहले चरण में, इनपुट एरे को <math>p</math> समान आकार के ब्लॉकों के <math>p</math> स्ट्राइप्स में विभाजित किया जाता है, प्रत्येक प्रोसेसर के लिए एक। प्रत्येक प्रोसेसर अतिरिक्त रूप से <math>k</math> बफर्स का आवंटन करता है जो ब्लॉकों के समान आकार के होते हैं, प्रत्येक बकेट के लिए एक। उसके बाद, प्रत्येक प्रोसेसर अपने स्ट्राइप को स्कैन करता है और तत्वों को उस अनुसार बफर में ले जाता है। अगर बफर भर गया है, तो बफर को प्रोसेसर के स्ट्राइप में लिखा जाता है, फ्रंट से शुरू करके। हमेशा कम से कम एक बफर के आकार का खाली स्थान होता है, क्योंकि बफर को लिखने के लिए (अर्थात बफर भर गया है), लिखे गए तत्वों से कम से कम एक बफर के आकार के तत्वों की जांच करने की आवश्यकता होती है। इसलिए, प्रत्येक भरा हुआ ब्लॉक एक ही बकेट के तत्वों को सम्मिलित करता है। स्कैन करते समय, प्रत्येक बकेट के आकार को ट्रैक किया जाता है।
+पहले चरण में, इनपुट एरे को <math>p</math> समान आकार के ब्लॉकों के <math>p</math> स्ट्राइप्स में विभाजित किया जाता है, प्रत्येक प्रोसेसर के लिए एक। प्रत्येक प्रोसेसर अतिरिक्त रूप से <math>k</math> बफर्स का आवंटन करता है जो ब्लॉकों के समान आकार के होते हैं, प्रत्येक बकेट के लिए एक। उसके बाद, प्रत्येक प्रोसेसर अपने स्ट्राइप को स्कैन करता है और एलमेंट को उस अनुसार बफर में ले जाता है। यदि बफर भर गया है, तो बफर को प्रोसेसर के स्ट्राइप में लिखा जाता है, फ्रंट से प्रारंभ करके। हमेशा कम से कम एक बफर के आकार का खाली स्थान होता है, क्योंकि बफर को लिखने के लिए (अर्थात बफर भर गया है), लिखे गए एलमेंट से कम से कम एक बफर के आकार के एलमेंट की जांच करने की आवश्यकता होती है। इसलिए, प्रत्येक भरा हुआ ब्लॉक एक ही बकेट के एलमेंट को सम्मिलित करता है। स्कैन करते समय, प्रत्येक बकेट के आकार को ट्रैक किया जाता है।
-[[Category:All articles with unsourced statements]]
-[[Category:Articles with invalid date parameter in template]]
-[[Category:Articles with unsourced statements from January 2018]]
-[[Category:Collapse templates]]
-[[Category:Created On 26/07/2023]]
-[[Category:Machine Translated Page]]
-[[Category:Navigational boxes| ]]
-[[Category:Navigational boxes without horizontal lists]]
-[[Category:Pages with script errors]]
-[[Category:Sidebars with styles needing conversion]]
 === ब्लॉक पर्म्यूटैशन ===
-सबसे पहले, एक उपसर्ग योग ऑपरेशन किया जाता है जो बकेट की सीमाओं की गणना करता है। यद्यपि, चूंकि इस चरण में केवल पूर्ण ब्लॉकों को स्थानांतरित किया जाता है, सीमाओं को ब्लॉक आकार के गुणक तक गोल किया जाता है और एक एकल अतिप्रवाह बफर आवंटित किया जाता है। ब्लॉक क्रमपरिवर्तन शुरू करने से पहले, कुछ खाली ब्लॉकों को इसकी बकेट के अंत में ले जाना पड़ सकता है। इसके बाद, एक सूचक लिखें <math>w_i</math> बकेट की शुरुआत पर सेट है <math>b_i</math> प्रत्येक बकेट के लिए उपऐरे और एक पठन सूचक <math>r_i</math> बकेट में अंतिम गैर-खाली ब्लॉक पर सेट किया गया है <math>b_i</math> प्रत्येक बकेट के लिए उपऐरे.
+सबसे पहले, प्रीफिक्स सम आपरेशन किया जाता है जो बकेटों की सीमाओं को निर्धारित करता है। हालांकि, इस चरण में केवल पूर्ण ब्लॉक ही ले जाए जाते हैं, इसलिए सीमाएं ब्लॉक आकार की गुणा के लिए बढ़ा दी जाती हैं और एक एकल ओवरफ्लो बफर आवंटित की जाती है। ब्लॉक परिवर्तन प्रारंभ करने से पहले, कुछ खाली ब्लॉक बकेट के अंत में ले जाए जाने की आवश्यकता हो सकती है। इसके बाद, प्रत्येक बकेट के लिए एक लेखन सूचकांक <math>w_i</math> सेट किया जाता है जो बकेट <math>b_i</math> उपसूचकांश के प्रारंभ पर सेट किया जाता है और प्रत्येक बकेट के लिए एक पठन सूचकांक <math>r_i</math> सेट किया जाता है जो बकेट <math>b_i</math> उपसूचकांश के अंतिम खाली ब्लॉक में सेट किया जाता है।
-कार्य विवाद को सीमित करने के लिए, प्रत्येक प्रोसेसर को एक अलग प्राथमिक बकेट सौंपा गया है <math>b_{prim}</math> और दो स्वैप बफ़र्स जो प्रत्येक ब्लॉक को पकड़ सकते हैं। प्रत्येक चरण में, यदि दोनों स्वैप बफ़र खाली हैं, तो प्रोसेसर रीड पॉइंटर को कम कर देता है <math>r_{prim}</math> इसके प्राथमिक बकेट का और ब्लॉक को पढ़ता है <math>r_{prim - 1}</math> और इसे अपने स्वैप बफ़र्स में से एक में रखता है। गंतव्य बकेट निर्धारित करने के बाद <math>b_{dest}</math> ब्लॉक के पहले तत्व को वर्गीकृत करके, यह राइट पॉइंटर को बढ़ाता है <math>w_{dest}</math>, पर ब्लॉक पढ़ता है <math>w_{dest - 1}</math> दूसरे स्वैप बफ़र में और ब्लॉक को उसके गंतव्य बकेट में लिखता है। अगर <math>w_{dest} > r_{dest}</math>, स्वैप बफ़र्स फिर से खाली हैं। अन्यथा स्वैप बफ़र्स में बचे ब्लॉक को उसके गंतव्य बकेट में डालना होगा।
+वर्क कन्टेन्शन की सीमा निर्धारित करने के लिए, प्रत्येक प्रोसेसर को एक अलग-अलग प्राथमिक बकेट <math>b_{prim}</math> और दो स्वैप बफर दिए जाते हैं, जो प्रत्येक में एक ब्लॉक हो सकता है। प्रत्येक चरण में, यदि दोनों स्वैप बफर खाली होते हैं, तो प्रोसेसर अपने प्राथमिक बकेट के पठन सूचकांक <math>r_{prim}</math> को कम करता है और एक ब्लॉक को <math>r_{prim - 1}</math> पर पढ़ता है और इसे अपने स्वैप बफर में स्थानांतरित करता है। ब्लॉक का गंतव्य बकेट <math>b_{dest}</math> तय करने के बाद, प्रारंभ में ब्लॉक का वर्तमान स्थानांतरित करते समय प्रोसेसर ब्लॉक के पहले तत्व की श्रेणीबद्धता से गंतव्य बकेट को निर्धारित करता है। फिर वह लेखन सूचकांक <math>w_{dest}</math> को बढ़ाता है, <math>w_{dest - 1}</math> पर ब्लॉक पढ़ता है और ब्लॉक को अपने गंतव्य बकेट में लिखता है। यदि <math>w_{dest} > r_{dest}</math> है, तो स्वैप बफर्स फिर से खाली हो जाते हैं। अन्यथा, स्वैप बफर्स में बचे रहे ब्लॉक को अपने गंतव्य बकेट में डालना अवश्यक होता है।
 यदि किसी प्रोसेसर की प्राथमिक बकेट की उपऐरे में सभी ब्लॉक सही बकेट में हैं, तो अगली बकेट को प्राथमिक बकेट के रूप में चुना जाता है। यदि कोई प्रोसेसर एक बार सभी बकेट को प्राथमिक बकेट के रूप में चुनता है, तो प्रोसेसर समाप्त हो जाता है।
-=== सफ़ाई ===
-चूँकि ब्लॉक क्रमपरिवर्तन चरण में केवल पूरे ब्लॉकों को स्थानांतरित किया गया था, कुछ तत्व अभी भी गलत तरीके से बकेट सीमाओं के आसपास रखे जा सकते हैं। चूंकि प्रत्येक तत्व के लिए ऐरे में पर्याप्त जगह होनी चाहिए, उन गलत तरीके से रखे गए एलमेंट को बाएं से दाएं खाली स्थानों पर ले जाया जा सकता है, अंत में ओवरफ्लो बफर पर विचार किया जा सकता है।
+=== क्लीनअप ===
+चूँकि ब्लॉक क्रमपरिवर्तन चरण में केवल पूरे ब्लॉकों को स्थानांतरित किया गया था, कुछ तत्व अभी भी गलत विधि से बकेट सीमाओं के निकट रखे जा सकते हैं। चूंकि प्रत्येक तत्व के लिए ऐरे में पर्याप्त स्पेस होना चाहिए, उन गलत विधि से रखे गए एलमेंट को बाएं से दाएं खाली स्थानों पर ले जाया जा सकता है, अंत में ओवरफ्लो बफर पर विचार किया जा सकता है।
 == यह भी देखें ==
 * [[फ्लैशसॉर्ट]]
-* जल्दी से सुलझाएं
+* क्विकसॉर्ट
 ==संदर्भ==
@@ Line 218: / Line 229: @@
 {{sorting}}
-[[Category: छँटाई एल्गोरिदम]] [[Category: वितरित एल्गोरिदम]]
+[[Category:All articles with unsourced statements]]
+[[Category:Articles with invalid date parameter in template]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with unsourced statements from January 2018]]
+[[Category:Collapse templates]]
 [[Category:Created On 26/07/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages with script errors]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates using TemplateData]]
+[[Category:Wikipedia metatemplates]]
+[[Category:छँटाई एल्गोरिदम]]
+[[Category:वितरित एल्गोरिदम]]

Anonymous

Search

सैंपलसॉर्ट: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 13:52, 14 August 2023

Contents

एल्गोरिथम

स्यूडोकोड

कम्प्लेक्सिटी