सैंपलसॉर्ट: 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(p)

सभी नोड्स को रीड करने के लिए

O(\log(p))

ब्रॉड्कैस्टिंग के लिए

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

सभी कीज के लिए बाइनरी सर्च हेतु

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

बकेट में 'की' भेजने के लिए

बकेट को क्रमबद्ध करें.

O\left(c\left({\frac {n}{p}}\right)\right)

जहाँ

c(n)

अंतर्निहित अनुक्रमिक सॉर्टिंग पद्धति की कम्प्लेक्सिटी है।^[1] प्रायः

c(n)=n\log(n)

.

इस एल्गोरिथम द्वारा की गई तुलनाओं की संख्या, सूचना सैद्धांतिक इष्टतम $\log _{2}(n!)$ के निकट पहुंचती है बड़े इनपुट अनुक्रमों के लिए. फ़्रेज़र और मैककेलर द्वारा किए गए प्रयोगों में, एल्गोरिदम को क्विकसॉर्ट की तुलना में 15% कम तुलना की आवश्यकता थी।

डेटा सैंपलिंग

डेटा का सैम्पल विभिन्न विधियों से लिया जा सकता है। कुछ विधियों में सम्मिलित हैं:

समान दूरी वाले सैम्पल चुनें.
यादृच्छिक विधि से चयनित सैम्पल चुनें.

ओवरसैंपलिंग

ओवरसैंपलिंग अनुपात यह निर्धारित करता है कि स्प्लिटर्स को निर्धारित करने से पहले सैम्पल के रूप में कितनी बार अधिक डेटा एलमेंट को प्राप्त करना है। इसका लक्ष्य डेटा के वितरण का अच्छा प्रतिनिधित्व प्राप्त करना है। यदि डेटा मान व्यापक रूप से वितरित हैं, जिसमें कई डुप्लिकेट मान नहीं हैं, तो एक छोटा सैम्पल अनुपात पर्याप्त है। अन्य परिस्थितियों में जहां वितरण में कई डुप्लिकेट हैं, एक बड़ा ओवरसैंपलिंग अनुपात आवश्यक होगा। आदर्श स्थिति में, चरण 2 के उपरांत, प्रत्येक बकेट में $n/p$ एलेमेन्ट सम्मिलित होता है। इस परिप्रेक्ष्य में, किसी भी बकेट को सॉर्ट करने में अन्य की तुलना में अधिक समय नहीं लगता है, क्योंकि सभी बकेट समान आकार के होतें हैं।

आवश्यकता से $k$ बार अधिक सैंपल निकालने के उपरांत, सैंपल सॉर्ट किया जाता है। इसके उपरांत, बकेट सीमाओं के रूप में उपयोग किए जाने वाले स्प्लिटर्स स्थिति में $k,2k,3k,\dots ,(p-1)k$ सैम्पल हैं। यह केवल चयन करने की तुलना में अच्छे स्प्लिटर्स के लिए उपयुक्त अनुमान प्रदान करता है तथा $p$ यादृच्छिक विधि से विभाजित हो जाता है।

बकेट आकार अनुमान

परिणामी सैम्पल आकार के साथ, अपेक्षित बकेट आकार और विशेष रूप से एक निश्चित आकार से अधिक बकेट की संभावना का अनुमान लगाया जा सकता है। निम्नलिखित यह दिखाएगा कि ओवरसैंपलिंग कारक के लिए $S\in \Theta \left({\dfrac {\log n}{\epsilon ^{2}}}\right)$ किसी भी बकेट में इससे अधिक न होने की प्रायिकता $(1+\epsilon )\cdot {\dfrac {n}{p}}$ $1-{\dfrac {1}{n}}$ एलमेंट से ज्यादा है।

यह सिद्ध करने के लिए हम सॉर्टिड सीक्वन्स $\langle e_{1},\dots ,e_{n}\rangle$ के रूप में इनपुट लेते हैं। प्रोसेसर को $(1+\epsilon )\cdot n/p$ से अधिक एलमेंट प्राप्त करने के लिए, $(1+\epsilon )\cdot n/p$ लंबाई का एक ऐसा उपसूत्र होना आवश्यक है, जिसमें से अधिकतम $S$ सैंपल्स चुने जाते हैं। ये तथ्य $P_{\text{fail}}$ संभाव्यता का गठन करते हैं। इसे यादृच्छिक चर के रूप में निम्नलिखित रूप से दर्शाया जा सकता है:

X_{i}:={\begin{cases}1,&{\text{if }}s_{i}\in \left\langle e_{j},\dots ,e_{j}+(1+\epsilon )\cdot {\dfrac {n}{p}}\right\rangle \\0,&{\text{otherwise}}\end{cases}},X:=\sum _{i=0}^{S\cdot p-1}X_{i}

के अपेक्षित मूल्य के लिए

X_{i}

धारण करता है:

E(X_{i})=P(X_{i}=1)={\dfrac {1+\epsilon }{p}}

इसका उपयोग अनुमान लगाने के लिए किया जाएगा

P_{\text{fail}}

:

P(X<S)\approx P(X<(1-\epsilon ^{2})S)=P(X<(1-\epsilon )E(X))

अब चेर्नॉफ़ बाध्य का उपयोग करके, इसे दिखाया जा सकता है:

P_{\text{fail}}=n\cdot P(X<S)\leq n\cdot \exp \left({\dfrac {-\epsilon ^{2}\cdot S}{2}}\right)\leq n\cdot {\dfrac {1}{n^{2}}}{\text{ for }}S\geq {\dfrac {4}{\epsilon ^{2}}}\ln n

कई इडेंटिकल 'की'(key)

कई इडेंटिकल 'की' के परिप्रेक्ष्य में, एल्गोरिदम कई पुनरावर्तन स्तरों से गुजरता है जहां अनुक्रमों को क्रमबद्ध किया जाता है, क्योंकि पूरे अनुक्रम में समान कुंजियाँ होती हैं। समानता बकेट प्रारंभ करके इसका प्रतिकार किया जा सकता है। पोल के बराबर एलमेंट को उनके संबंधित समानता बकेट में क्रमबद्ध किया जाता है, जिसे केवल एक अतिरिक्त सशर्त शाखा के साथ कार्यान्वित किया जा सकता है। समानता के बकेट आगे क्रमबद्ध नहीं हैं। यह काम करता है, क्योंकि कुंजियाँ अधिक से अधिक $n/k$ घटित होती हैं। इसमे समय के निर्णायक बनने की संभावना है।

पैरलेल सिस्टम में उपयोग

समानांतर सैम्पल सॉर्ट का उदाहरण

p=3

प्रोसेसर और एक ओवरसैंपलिंग कारक

k=3

.

सैंपलसॉर्ट का उपयोग प्रायः पैरलेल सिस्टम में किया जाता है, जिसमें वितरित कंप्यूटिंग जैसे कि बल्क सिंक्रोनस पैरलेल मशीने सम्मिलित हैं।^[6]^[4]^[7] स्प्लिटर्स की परिवर्तनीय मात्रा (क्विकसॉर्ट में केवल एक पोल के विपरीत) के कारण, सैंपलसॉर्ट समानांतरीकरण और स्केलिंग के लिए बहुत उपयुक्त और सहज है। इसके अतिरिक्त सैंपलसॉर्ट भी उदाहरण के कार्यान्वयन की तुलना में अधिक कैश-एफीसिएंट है।

पैरललीकरण को प्रत्येक प्रोसेसर या नोड के लिए विभाजित करके अंगीकृत किया जाता है, जहां बकेटों की संख्या प्रोसेसरों की संख्या $p$ के बराबर होती है। सैंपलसॉर्ट पैरलल सिस्टम में प्रभावी होता है क्योंकि प्रत्येक प्रोसेसर को लगभग समान बकेट का आकार $n/p$ प्राप्त होता है। बकेट समानांतर सॉर्ट किए जाते हैं, इसलिए प्रोसेसर लगभग समान समय में सॉर्टिंग पूरा कर जाते हैं, इससे किसी प्रोसेसर को दूसरों के लिए रुकने की आवश्यकता नहीं होती है।

वितरित सिस्टम पर, स्प्लिटर्स का चयन $k$ एलमेंट को प्रत्येक प्रोसेसर पर लेकर किया जाता है, परिणामस्वरूप बने $kp$ एलमेंट को वितरित सॉर्टिंग एल्गोरिदम के साथ सॉर्ट किया जाता है, हर $k$ -वां तत्व चुना जाता है और परिणाम को सभी प्रोसेसरों को ब्रॉडकास्ट किया जाता है। यह $p$ प्रोसेसरों पर $kp$ एलमेंट को सॉर्ट करने के लिए $T_{\text{sort}}(kp,p)$ का खर्च होता है, साथ ही $p$ चुने गए स्प्लिटर्स को $p$ प्रोसेसरों को वितरित करने के लिए $T_{\text{allgather}}(p,p)$ का भी कॉस्ट होता है।

परिणामकारी स्प्लिटर्स के साथ, प्रत्येक प्रोसेसर अपने इनपुट डेटा को स्थानीय बकेट में रखता है। इसके लिए बाइनरी सर्च के साथ ${\mathcal {O}}(n/p\log p)$ का समय लगता है। इसके बाद, स्थानीय बकेट्स प्रोसेसरों को पुनः वितरित किए जाते हैं। प्रोसेसर $i$ सभी अन्य प्रोसेसरों के स्थानीय बकेट्स $b_{i}$ को प्राप्त करता है और इन्हें स्थानीय रूप से सॉर्ट करता है। वितरण $T_{\text{all-to-all}}(N,p)$ समय लेता है, जहां $N$ सबसे बड़े बकेट का आकार है। स्थानीय सॉर्ट $T_{\text{localsort}}(N)$ का समय लेता है।

1990 के दशक में कनेक्शन मशीन सुपरकंप्यूटर पर किए गए प्रयोग ने दिखाया कि सैंपलसॉर्ट बड़े डेटासेट को सॉर्ट करने में विशेष रूप से अच्छा है, क्योंकि इसका इंटरप्रोसेसर संचार ओवरहेड कम होता है।^[8] हाल के GPUs पर, इस एल्गोरिदम का प्रयोग उसके विकल्पों की तुलना में कम प्रभावी हो सकता है।^[9]

सैम्पल सॉर्ट का एफीसिएंट कार्यान्वयन

सुपर स्केलर सैंपलसॉर्ट का एनिमेटेड उदाहरण। प्रत्येक चरण में, जिन संख्याओं की तुलना की जाती है उन्हें नीले रंग से चिह्नित किया जाता है और जो संख्याएं अन्यथा रीड या राइट कीजाती हैं उन्हें लाल रंग से चिह्नित किया जाता है।

जैसा कि ऊपर बताया गया है, सैंपलसॉर्ट एल्गोरिदम चयनित स्प्लिटर्स के अनुसार एलमेंट को विभाजित करता है। पेपर सुपर स्केलर सैंपल सॉर्ट में एक एफीसिएंट कार्यान्वयन रणनीति प्रस्तावित है।^[5]पेपर में प्रस्तावित कार्यान्वयन $n$ एफीसिएंट कार्यान्वयन के लिए (इनपुट डेटा युक्त मूल ऐरे और एक अस्थायी) आकार की दो ऐरे का उपयोग करता है । इसलिए, कार्यान्वयन का यह संस्करण इन-प्लेस एल्गोरिदम नहीं है।

प्रत्येक रिकर्सन चरण में, डेटा को डिवाइड विधि से अन्य ऐरे में कॉपी किया जाता है। यदि डेटा अंतिम रिकर्सन चरण में अस्थायी ऐरे में है, तो डेटा को मूल ऐरे में वापस कॉपी किया जाता है।

बकेट का निर्धारण

किसी तुलना-आधारित सॉर्टिंग एल्गोरिदम में तुलना की संचार ऑपरेशन सबसे प्रदर्शन-मुख्य भाग होती है। सैंपलसॉर्ट में यह तत्व के लिए बकेट निर्धारित करने के लिए होती है। इसमें प्रत्येक तत्व के लिए $\log k$ समय लगता है।

सुपर स्केलर सैंपल सॉर्ट एक बैलन्स सर्च ट्री का उपयोग करता है जो स्वतः में एक एरे $t$ में रखा गया होता है। रूट ट्री 0 पर रखा जाता है, $t_{i}$ का बाईं उत्तरधारी $t_{2i}$ पर रखा जाता है और दाईं उत्तरधारी $t_{2i+1}$ पर रखा जाता है। ट्री $t$ को दिया गया है, एल्गोरिदम एलमेंट $a_{i}$ का बकेट नंबर $j$ निम्नलिखित विधि से निर्धारित करता है (यहां स्वीकृति है कि $a_{i}>t_{j}$ का मूल्य 1 होगा यदि यह सत्य है और 0 होगा यदि यह सत्य नहीं है):

j := 1
repeat log₂(p) times
    j := 2j + (a > t_j)
j := j − p + 1

बकेटों की संख्या $k$ कंपाइल समय पर ज्ञात होती है, इसलिए कंपाइलर इस लूप को अनरोल कर सकता है। तुलना ऑपरेशन को प्रेडिकेटेड इंस्ट्रक्शन्स के साथ लागू किया जाता है। इससे ब्रांच मिसप्रिडिक्शन नहीं होती है, जो तुलना ऑपरेशन को काफी धीमा बना सकता है।

विभाजन

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

इस दोहराने वाले तुलना को टालने के लिए, सुपर स्केलर सैंपल सॉर्ट एक अतिरिक्त एरे $o$ (जिसे ऑरेकल कहा जाता है) का उपयोग करता है जो प्रत्येक तत्व के एक बकेट से सम्बंधित होता है। पहले, एल्गोरिदम $o$ के संदर्भ को निर्धारित करके यह निर्धारित करता है, फिर बकेट का आकार निर्धारित करके एलमेंट को $o$ द्वारा निर्धारित बकेट में रखता है। एरे $o$ भी संग्रह स्थान में खर्च करता है, परंतु क्योंकि इसमें केवल $n\cdot \log k$ बिट संभावित होते हैं, इन खर्चों को इनपुट एरे के अनुपात में छोटा माना जा सकता है।

इन-प्लेस सैंपलसॉर्ट

ऊपर दिखाए गए एफीसिएंट सैंपलसॉर्ट कार्यान्वयन की एक मुख्य हानि यह है कि यह इन-प्लेस नहीं है और सॉर्टिंग के समय इनपुट अनुक्रम के समान आकार की दूसरी अस्थायी ऐरे की आवश्यकता होती है। उदाहरण के लिए एफीसिएंट कार्यान्वयन क्विकसॉर्ट इन-प्लेस हैं और इस प्रकार अधिक प्लेस एफीसिएंट हैं। यद्यपि, सैंपलसॉर्ट को इन-प्लेस पर भी लागू किया जा सकता है।^[10]

इन-प्लेस एल्गोरिदम को चार चरणों में विभाजित किया गया है:

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

इस एल्गोरिदम की एक स्पष्ट हानि यह है कि यह प्रत्येक तत्व को दो बार रीड और राइट करता है, एक बार वर्गीकरण चरण में और एक बार ब्लॉक क्रमपरिवर्तन चरण में। यद्यपि, एल्गोरिथ्म अन्य अत्याधुनिक इन-प्लेस प्रतिस्पर्धियों की तुलना में तीन गुना तेज और अन्य अत्याधुनिक अनुक्रमिक प्रतिस्पर्धियों की तुलना में 1.5 गुना तेज प्रदर्शन करता है। जैसा कि सैम्पल के बारे में पहले ही ऊपर चर्चा की जा चुकी है, बाद के तीन चरणों के बारे में आगे विस्तार से बताया जाएगा।

स्थानीय वर्गीकरण

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

ब्लॉक पर्म्यूटैशन

सबसे पहले, प्रीफिक्स सम आपरेशन किया जाता है जो बकेटों की सीमाओं को निर्धारित करता है। हालांकि, इस चरण में केवल पूर्ण ब्लॉक ही ले जाए जाते हैं, इसलिए सीमाएं ब्लॉक आकार की गुणा के लिए बढ़ा दी जाती हैं और एक एकल ओवरफ्लो बफर आवंटित की जाती है। ब्लॉक परिवर्तन प्रारंभ करने से पहले, कुछ खाली ब्लॉक बकेट के अंत में ले जाए जाने की आवश्यकता हो सकती है। इसके बाद, प्रत्येक बकेट के लिए एक लेखन सूचकांक $w_{i}$ सेट किया जाता है जो बकेट $b_{i}$ उपसूचकांश के प्रारंभ पर सेट किया जाता है और प्रत्येक बकेट के लिए एक पठन सूचकांक $r_{i}$ सेट किया जाता है जो बकेट $b_{i}$ उपसूचकांश के अंतिम खाली ब्लॉक में सेट किया जाता है।

वर्क कन्टेन्शन की सीमा निर्धारित करने के लिए, प्रत्येक प्रोसेसर को एक अलग-अलग प्राथमिक बकेट $b_{prim}$ और दो स्वैप बफर दिए जाते हैं, जो प्रत्येक में एक ब्लॉक हो सकता है। प्रत्येक चरण में, यदि दोनों स्वैप बफर खाली होते हैं, तो प्रोसेसर अपने प्राथमिक बकेट के पठन सूचकांक $r_{prim}$ को कम करता है और एक ब्लॉक को $r_{prim-1}$ पर पढ़ता है और इसे अपने स्वैप बफर में स्थानांतरित करता है। ब्लॉक का गंतव्य बकेट $b_{dest}$ तय करने के बाद, प्रारंभ में ब्लॉक का वर्तमान स्थानांतरित करते समय प्रोसेसर ब्लॉक के पहले तत्व की श्रेणीबद्धता से गंतव्य बकेट को निर्धारित करता है। फिर वह लेखन सूचकांक $w_{dest}$ को बढ़ाता है, $w_{dest-1}$ पर ब्लॉक पढ़ता है और ब्लॉक को अपने गंतव्य बकेट में लिखता है। यदि $w_{dest}>r_{dest}$ है, तो स्वैप बफर्स फिर से खाली हो जाते हैं। अन्यथा, स्वैप बफर्स में बचे रहे ब्लॉक को अपने गंतव्य बकेट में डालना अवश्यक होता है।

यदि किसी प्रोसेसर की प्राथमिक बकेट की उपऐरे में सभी ब्लॉक सही बकेट में हैं, तो अगली बकेट को प्राथमिक बकेट के रूप में चुना जाता है। यदि कोई प्रोसेसर एक बार सभी बकेट को प्राथमिक बकेट के रूप में चुनता है, तो प्रोसेसर समाप्त हो जाता है।

क्लीनअप

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

यह भी देखें

फ्लैशसॉर्ट
क्विकसॉर्ट

संदर्भ

↑ ^1.0 ^1.1 "मानक टेम्पलेट अनुकूली समानांतर लाइब्रेरी का उपयोग करके नमूना सॉर्ट करें" (PDF) (Technical report). Texas A&M University.
↑ Grama, Ananth; Karypis, George; Kumar, Vipin (2003). "9.5 Bucket and Sample Sort". समानांतर कंप्यूटिंग का परिचय (2nd ed.). ISBN 0-201-64865-2. Archived from the original on 2016-12-13. Retrieved 2014-10-28.
↑ ^3.0 ^3.1 Frazer, W. D.; McKellar, A. C. (1970-07-01). "Samplesort: A Sampling Approach to Minimal Storage Tree Sorting". Journal of the ACM. 17 (3): 496–507. doi:10.1145/321592.321600. S2CID 16958223.
↑ ^4.0 ^4.1 Hill, Jonathan M. D.; McColl, Bill; Stefanescu, Dan C.; Goudreau, Mark W.; Lang, Kevin; Rao, Satish B.; Suel, Torsten; Tsantilas, Thanasis; Bisseling, Rob H. (1998). "BSPlib: The BSP Programming Library". Parallel Computing. 24 (14): 1947–1980. CiteSeerX 10.1.1.48.1862. doi:10.1016/S0167-8191(98)00093-3.
↑ ^5.0 ^5.1 Sanders, Peter; Winkel, Sebastian (2004-09-14). "Super Scalar Sample Sort". Algorithms – ESA 2004. Lecture Notes in Computer Science. Vol. 3221. pp. 784–796. CiteSeerX 10.1.1.68.9881. doi:10.1007/978-3-540-30140-0_69. ISBN 978-3-540-23025-0.
↑ Gerbessiotis, Alexandros V.; Valiant, Leslie G. (1992). "डायरेक्ट बल्क-सिंक्रोनस समानांतर एल्गोरिदम". J. Parallel and Distributed Computing. 22: 22–251. CiteSeerX 10.1.1.51.9332.
↑ Hightower, William L.; Prins, Jan F.; Reif, John H. (1992). बड़ी समानांतर मशीनों पर यादृच्छिक छँटाई का कार्यान्वयन (PDF). ACM Symp. on Parallel Algorithms and Architectures.
↑ Blelloch, Guy E.; Leiserson, Charles E.; Maggs, Bruce M.; Plaxton, C. Gregory; Smith, Stephen J.; Zagha, Marco (1991). A Comparison of Sorting Algorithms for the Connection Machine CM-2. ACM Symp. on Parallel Algorithms and Architectures. CiteSeerX 10.1.1.131.1835.
↑ Satish, Nadathur; Harris, Mark; Garland, Michael. Designing Efficient Sorting Algorithms for Manycore GPUs. Proc. IEEE Int'l Parallel and Distributed Processing Symp. CiteSeerX 10.1.1.190.9846.
↑ Axtmann, Michael; Witt, Sascha; Ferizovic, Daniel; Sanders, Peter (2017). "इन-प्लेस पैरेलल सुपर स्केलर सैंपलसॉर्ट (IPSSSSo)". 25th Annual European Symposium on Algorithms (ESA 2017). 87 (Leibniz International Proceedings in Informatics (LIPIcs)): 9:1–9:14. doi:10.4230/LIPIcs.ESA.2017.9.

बाहरी संबंध

Frazer and McKellar's samplesort and derivatives:

Adapted for use on parallel computers:

[sample_sort_tr.pdf-1] 1.0 ^1.1 "मानक टेम्पलेट अनुकूली समानांतर लाइब्रेरी का उपयोग करके नमूना सॉर्ट करें" (PDF) (Technical report). Texas A&M University.

[2] Grama, Ananth; Karypis, George; Kumar, Vipin (2003). "9.5 Bucket and Sample Sort". समानांतर कंप्यूटिंग का परिचय (2nd ed.). ISBN 0-201-64865-2. Archived from the original on 2016-12-13. Retrieved 2014-10-28.

[Frazer70-3] 3.0 ^3.1 Frazer, W. D.; McKellar, A. C. (1970-07-01). "Samplesort: A Sampling Approach to Minimal Storage Tree Sorting". Journal of the ACM. 17 (3): 496–507. doi:10.1145/321592.321600. S2CID 16958223.

[hill-4] 4.0 ^4.1 Hill, Jonathan M. D.; McColl, Bill; Stefanescu, Dan C.; Goudreau, Mark W.; Lang, Kevin; Rao, Satish B.; Suel, Torsten; Tsantilas, Thanasis; Bisseling, Rob H. (1998). "BSPlib: The BSP Programming Library". Parallel Computing. 24 (14): 1947–1980. CiteSeerX 10.1.1.48.1862. doi:10.1016/S0167-8191(98)00093-3.

[:0-5] 5.0 ^5.1 Sanders, Peter; Winkel, Sebastian (2004-09-14). "Super Scalar Sample Sort". Algorithms – ESA 2004. Lecture Notes in Computer Science. Vol. 3221. pp. 784–796. CiteSeerX 10.1.1.68.9881. doi:10.1007/978-3-540-30140-0_69. ISBN 978-3-540-23025-0.

[6] Gerbessiotis, Alexandros V.; Valiant, Leslie G. (1992). "डायरेक्ट बल्क-सिंक्रोनस समानांतर एल्गोरिदम". J. Parallel and Distributed Computing. 22: 22–251. CiteSeerX 10.1.1.51.9332.

[7] Hightower, William L.; Prins, Jan F.; Reif, John H. (1992). बड़ी समानांतर मशीनों पर यादृच्छिक छँटाई का कार्यान्वयन (PDF). ACM Symp. on Parallel Algorithms and Architectures.

[8] Blelloch, Guy E.; Leiserson, Charles E.; Maggs, Bruce M.; Plaxton, C. Gregory; Smith, Stephen J.; Zagha, Marco (1991). A Comparison of Sorting Algorithms for the Connection Machine CM-2. ACM Symp. on Parallel Algorithms and Architectures. CiteSeerX 10.1.1.131.1835.

[9] Satish, Nadathur; Harris, Mark; Garland, Michael. Designing Efficient Sorting Algorithms for Manycore GPUs. Proc. IEEE Int'l Parallel and Distributed Processing Symp. CiteSeerX 10.1.1.190.9846.

[10] Axtmann, Michael; Witt, Sascha; Ferizovic, Daniel; Sanders, Peter (2017). "इन-प्लेस पैरेलल सुपर स्केलर सैंपलसॉर्ट (IPSSSSo)". 25th Annual European Symposium on Algorithms (ESA 2017). 87 (Leibniz International Proceedings in Informatics (LIPIcs)): 9:1–9:14. doi:10.4230/LIPIcs.ESA.2017.9.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

v t e Sorting algorithms
Theory	Computational complexity theory Big O notation Total order Lists Inplacement Stability Comparison sort Adaptive sort Sorting network Integer sorting X + Y sorting Transdichotomous model Quantum sort
Exchange sorts	Bubble sort Cocktail shaker sort Odd–even sort Comb sort Gnome sort Proportion extend sort Quicksort Slowsort Stooge sort Bogosort
Selection sorts	Selection sort Heapsort Smoothsort Cartesian tree sort Tournament sort Cycle sort Weak-heap sort
Insertion sorts	Insertion sort Shellsort Splaysort Tree sort Library sort Patience sorting
Merge sorts	Merge sort Cascade merge sort Oscillating merge sort Polyphase merge sort
Distribution sorts	American flag sort Bead sort Bucket sort Burstsort Counting sort Interpolation sort Pigeonhole sort Proxmap sort Radix sort Flashsort
Concurrent sorts	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network Samplesort
Hybrid sorts	Block merge sort Kirkpatrick–Reisch sort Timsort Introsort Spreadsort Merge-insertion sort
Other	Topological sorting Pre-topological order Pancake sorting Spaghetti sort

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 13:52, 14 August 2023

Contents

एल्गोरिथम

स्यूडोकोड

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

डेटा सैंपलिंग

ओवरसैंपलिंग

बकेट आकार अनुमान

कई इडेंटिकल 'की'(key)

पैरलेल सिस्टम में उपयोग

सैम्पल सॉर्ट का एफीसिएंट कार्यान्वयन

बकेट का निर्धारण

विभाजन

इन-प्लेस सैंपलसॉर्ट

स्थानीय वर्गीकरण

ब्लॉक पर्म्यूटैशन

क्लीनअप

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

@@ Line 1: / Line 1: @@
-सैंपलसॉर्ट एक [[छँटाई एल्गोरिथ्म]] है जो एक विभाजन और जीत एल्गोरिथ्म है जो अक्सर समानांतर प्रसंस्करण प्रणालियों में उपयोग किया जाता है।<ref name="sample_sort_tr.pdf">{{cite web |url=http://www.cra.org/Activities/craw_archive/dmp/awards/2007/Berlin/jberlin/sample_sort_tr.pdf |title=मानक टेम्पलेट अनुकूली समानांतर लाइब्रेरी का उपयोग करके नमूना सॉर्ट करें|publisher=Texas A&M University |type=Technical report}}</ref> पारंपरिक विभाजन और जीत सॉर्टिंग एल्गोरिदम सरणी को उप-अंतराल या बकेट में विभाजित करता है। फिर बाल्टियों को अलग-अलग क्रमबद्ध किया जाता है और फिर एक साथ जोड़ दिया जाता है। हालाँकि, यदि सरणी को गैर-समान रूप से वितरित किया जाता है, तो इन सॉर्टिंग एल्गोरिदम का प्रदर्शन काफी हद तक कम हो सकता है। सैंपलसॉर्ट आकार का एक नमूना चुनकर इस समस्या का समाधान करता है {{mvar|s}} से {{mvar|n}}-तत्व अनुक्रम, और नमूने को क्रमबद्ध करके और चुनकर बाल्टियों की सीमा का निर्धारण करना {{math|''p''−1 &lt; ''s''}} परिणाम से तत्व। ये तत्व (जिन्हें स्प्लिटर्स कहा जाता है) फिर सरणी को विभाजित करते हैं {{mvar|p}} लगभग बराबर आकार की बाल्टियाँ।<ref>{{cite book |title=समानांतर कंप्यूटिंग का परिचय|edition=2nd |chapter-url=http://parallelcomp.uw.hu/ch09lev1sec5.html |chapter=9.5 Bucket and Sample Sort |first1=Ananth |last1=Grama |first2=George |last2=Karypis |first3=Vipin |last3=Kumar |year=2003 |isbn=0-201-64865-2 |access-date=2014-10-28 |archive-date=2016-12-13 |archive-url=https://web.archive.org/web/20161213114412/http://parallelcomp.uw.hu/ch09lev1sec5.html |url-status=dead }}</ref> सैंपलसॉर्ट का वर्णन 1970 के पेपर, सैंपलसॉर्ट: ए सैंपलिंग अप्रोच टू मिनिमल स्टोरेज ट्री सॉर्टिंग में डब्ल्यू. डी. फ्रेज़र और ए. सी. मैककेलर द्वारा किया गया है।{{r|Frazer70}}
+'''सैंपलसॉर्ट''', डिवाइड एंड कंकर एल्गोरिथ्म पर आधारित एक [[छँटाई एल्गोरिथ्म|सॉर्टिंग एल्गोरिथ्म]] है, जिसका उपयोग प्रायः पैरलेल प्रोसेसिंग सिस्टम में किया जाता है।<ref name="sample_sort_tr.pdf">{{cite web |url=http://www.cra.org/Activities/craw_archive/dmp/awards/2007/Berlin/jberlin/sample_sort_tr.pdf |title=मानक टेम्पलेट अनुकूली समानांतर लाइब्रेरी का उपयोग करके नमूना सॉर्ट करें|publisher=Texas A&M University |type=Technical report}}</ref> पारंपरिक डिवाइड एंड कंकर एल्गोरिथ्म, ऐरे को सब-इंटरवल या बकेट में विभाजित करता है। फिर इस बकेट को अलग-अलग क्रमबद्ध किया जाता है और एक साथ जोड़ दिया जाता है। यद्यपि, यदि ये ऐरे गैर-समान रूप से वितरित किए गए है, तो इन सॉर्टिंग एल्गोरिदम का प्रदर्शन अत्यधिक सीमा तक कम हो सकता है। सैंपलसॉर्ट इस समस्या का समाधान करने में सक्षम है जिसमें n-एलिमेंट सीक्वन्स के लिए एक s आकार का सैम्पल चुनकर तथा उस सैंपल को सॉर्ट करने के उपरांत p-1 < s एलेमेन्ट को परिणाम से चुनकर बकेट की रेंज निर्धारित की जाती है। ये एलमेंट (जिन्हें स्प्लिटर्स कहा जाता है) फिर ऐरे को लगभग {{mvar|p}} समान बकेट में विभाजित करते हैं।<ref>{{cite book |title=समानांतर कंप्यूटिंग का परिचय|edition=2nd |chapter-url=http://parallelcomp.uw.hu/ch09lev1sec5.html |chapter=9.5 Bucket and Sample Sort |first1=Ananth |last1=Grama |first2=George |last2=Karypis |first3=Vipin |last3=Kumar |year=2003 |isbn=0-201-64865-2 |access-date=2014-10-28 |archive-date=2016-12-13 |archive-url=https://web.archive.org/web/20161213114412/http://parallelcomp.uw.hu/ch09lev1sec5.html |url-status=dead }}</ref> सैंपलसॉर्ट का वर्णन 1970 के लेख, सैंपलसॉर्ट: ए सैंपलिंग अप्रोच टू मिनिमल स्टोरेज ट्री सॉर्टिंग में डब्ल्यू. डी. फ्रेज़र और ए. सी. मैककेलर द्वारा किया गया है।{{r|Frazer70}}
 == एल्गोरिथम ==
-सैम्पल सॉर्ट क्विक सॉर्ट का सामान्यीकरण है। जहां [[जल्दी से सुलझाएं]] प्रत्येक चरण में अपने इनपुट को पिवट नामक एकल मान के आधार पर दो भागों में विभाजित करता है, सैंपलसॉर्ट इसके बजाय अपने इनपुट से एक बड़ा नमूना (आंकड़े) लेता है और अपने डेटा को तदनुसार बकेट में विभाजित करता है। क्विकसॉर्ट की तरह, यह फिर बाल्टियों को पुनरावर्ती रूप से सॉर्ट करता है।
+सैम्पल सॉर्ट क्विक सॉर्ट का सामान्यीकरण है। जहां [[जल्दी से सुलझाएं|क्विक सॉर्ट]] प्रत्येक चरण में अपने इनपुट को पिवट नामक एकल मान के आधार पर दो भागों में विभाजित करता है, सैंपलसॉर्ट इसके अतिरिक्त अपने इनपुट से एक बड़ा सैम्पल लेता है और अपने डेटा को तदनुसार बकेट में विभाजित करता है। क्विकसॉर्ट की तरह, यह फिर बकेट को पुनरावर्ती रूप से सॉर्ट करता है।
-सैंपलसॉर्ट कार्यान्वयन तैयार करने के लिए, किसी को बकेट की संख्या तय करने की आवश्यकता होती है {{mvar|p}}. जब यह किया जाता है, तो वास्तविक एल्गोरिदम तीन चरणों में संचालित होता है:{{r|hill}}
+सैंपलसॉर्ट कार्यान्वयन तैयार करने के लिए, हमें {{mvar|p}} बकेट की संख्या तय करने की आवश्यकता होती है। जब यह किया जाता है, तो वास्तविक एल्गोरिदम तीन चरणों में संचालित होता है:{{r|hill}}
-# नमूना {{math|''p''−1}} इनपुट से तत्व (स्प्लिटर्स)। इन्हें क्रमबद्ध करें; आसन्न स्प्लिटर्स की प्रत्येक जोड़ी फिर एक बाल्टी को परिभाषित करती है।
+# सैम्पल {{math|''p''−1}} इनपुट से तत्व (स्प्लिटर्स)। सॉर्ट करें; आसन्न स्प्लिटर्स का प्रत्येक युग्म फिर एक बकेट को परिभाषित करता है।
-# डेटा पर लूप करें, प्रत्येक तत्व को उपयुक्त बकेट में रखें। (इसका मतलब यह हो सकता है: इसे [[मल्टीप्रोसेसर]] सिस्टम में एक प्रोसेसर को भेजें।)
+# डेटा लूप करें, प्रत्येक तत्व को उपयुक्त बकेट में रखें। (इसका तात्पर्य यह हो सकता है: इसे [[मल्टीप्रोसेसर]] सिस्टम में एक प्रोसेसर को भेजें।)
-# प्रत्येक बाल्टी को क्रमबद्ध करें.
+# प्रत्येक बकेट को क्रमबद्ध करें.
 पूर्ण क्रमबद्ध आउटपुट बकेट का संयोजन है।
-एक आम रणनीति तय करना है {{mvar|p}} उपलब्ध प्रोसेसर की संख्या के बराबर। फिर डेटा को प्रोसेसर के बीच वितरित किया जाता है, जो कुछ अन्य, अनुक्रमिक, सॉर्टिंग एल्गोरिदम का उपयोग करके बकेट की सॉर्टिंग करते हैं।
+एक सामान्य रणनीति है कि p को उपलब्ध प्रोसेसरों के संख्या के बराबर रखा जाता है। फिर डेटा प्रोसेसरों के बीच वितरित किया जाता है, जो कुछ अन्य, अनुक्रमशील, सॉर्टिंग एल्गोरिदम का उपयोग करके बकेटों को क्रमबद्ध करते हैं।
 === स्यूडोकोड ===
-निम्नलिखित सूची उपर्युक्त तीन चरण वाले एल्गोरिदम को छद्मकोड के रूप में दिखाती है और दिखाती है कि एल्गोरिदम सिद्धांत रूप में कैसे काम करता है।<ref name=":0">{{cite book| last1=Sanders|first1=Peter| last2=Winkel|first2=Sebastian |title=Algorithms – ESA 2004 |chapter=Super Scalar Sample Sort | volume=3221|date=2004-09-14 | pages=784–796 | doi=10.1007/978-3-540-30140-0_69 | series=Lecture Notes in Computer Science | isbn=978-3-540-23025-0| citeseerx=10.1.1.68.9881}}</ref> निम्नांकित में, {{mvar|A}} अवर्गीकृत डेटा है, {{mvar|k}} ओवरसैंपलिंग कारक है, जिस पर बाद में चर्चा की गई है, और {{mvar|p}} स्प्लिटर्स की संख्या है.
+निम्नलिखित सूची उपर्युक्त तीन चरण वाले एल्गोरिदम को स्यूडोकोड के रूप में प्रदर्शित करती है और दिखाती है कि एल्गोरिदम सिद्धांत रूप में कैसे कार्य करता है।<ref name=":0">{{cite book| last1=Sanders|first1=Peter| last2=Winkel|first2=Sebastian |title=Algorithms – ESA 2004 |chapter=Super Scalar Sample Sort | volume=3221|date=2004-09-14 | pages=784–796 | doi=10.1007/978-3-540-30140-0_69 | series=Lecture Notes in Computer Science | isbn=978-3-540-23025-0| citeseerx=10.1.1.68.9881}}</ref> निम्नांकित में, {{mvar|A}} अवर्गीकृत डेटा है, {{mvar|k}} ओवरसैंपलिंग कारक है, जिस पर बाद में चर्चा की गई है, और {{mvar|p}} स्प्लिटर्स की संख्या है.
-  फ़ंक्शन नमूनासॉर्ट(ए[1..एन], {{mvar|k}}, {{mvar|p}})
+  '''function''' sampleSort(A[1..n], {{mvar|k}}, {{mvar|p}})
-      // यदि औसत बाल्टी का आकार सीमा से नीचे है तो उदाहरण के लिए स्विच करें। जल्दी से सुलझाएं
+      // if average bucket size is below a threshold switch to e.g. quicksort
-      यदि ''एन'' / ''के'' <थ्रेसहोल्ड तो स्मॉलसॉर्ट(ए)
+      '''if''' ''n'' / ''k'' < threshold '''then''' smallSort(A)
-      /* स्टेप 1 */
+      /* Step 1 */
-      ''एस'' = [''एस'' चुनें<sub>1</sub>, ..., एस<sub>(''p''−1)''k''</sub>] यादृच्छिक रूप से // से नमूने चुनें
+      select ''S'' = [''S''<sub>1</sub>, ..., ''S''<sub>(''p''−1)''k''</sub>] randomly from // select samples
-      क्रम से लगाना {{mvar|S}} // सॉर्ट नमूना
+      sort {{mvar|S}} // sort sample
-      [एस<sub>0</sub>, एस<sub>1</sub>, ..., एस<sub>''p''−1</sub>, एस<sub>''p''</sub>] <- [-∞, एस<sub>''k''</sub>, एस<sub>2''k''</sub>, ..., एस<sub>(''p''−1)''k''</sub>, ∞] // स्प्लिटर्स का चयन करें
+      [''s''<sub>0</sub>, ''s''<sub>1</sub>, ..., s<sub>''p''−1</sub>, ''s''<sub>''p''</sub>] <- [-∞, ''S''<sub>''k''</sub>, ''S''<sub>2''k''</sub>, ..., ''S''<sub>(''p''−1)''k''</sub>, ∞] // select splitters
-      /* चरण दो */
+      /* Step 2 */
-      ''ए'' में प्रत्येक ''ए'' के लिए
+      '''for each''' ''a'' in ''A''
-          पाना {{mvar|j}} ऐसा कि एस<sub>''j''−1</sub> <ए <= एस<sub>''j''</sub>
+          find {{mvar|j}} such that ''s''<sub>''j''−1</sub> < ''a'' <= ''s''<sub>''j''</sub>
-जगह {{mvar|a}} बाल्टी में बी<sub>''j''</sub>
+         place {{mvar|a}} in bucket ''b''<sub>''j''</sub>
-/* चरण 3 और संयोजन */
+     /* Step 3 and concatenation */
-      रिटर्न कॉन्टेनेट(नमूनासॉर्ट(''बी''<sub>1</sub>), ..., नमूना सॉर्ट (बी<sub>''k''</sub>))
+      '''return''' concatenate(sampleSort(''b''<sub>1</sub>), ..., sampleSort(''b''<sub>''k''</sub>))
-छद्म कोड मूल फ्रेज़र और मैककेलर एल्गोरिदम से अलग है।<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> छद्म कोड में, सैंपलसॉर्ट को पुनरावर्ती रूप से कहा जाता है। फ़्रेज़र और मैककेलर ने केवल एक बार सैंपलसॉर्ट कहा और निम्नलिखित सभी पुनरावृत्तियों में क्विकसॉर्ट का उपयोग किया।
+स्यूडोकोड मूल फ्रेज़र और मैककेलर एल्गोरिदम से भिन्न है।<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> स्यूडोकोड में, सैंपलसॉर्ट को पुनरावर्ती रूप से कार्यवान्वित किया जाता है। फ़्रेज़र और मैककेलर ने केवल एक बार सैंपलसॉर्ट को कार्यान्वित किया और निम्नलिखित सभी पुनरावृत्तियों में क्विकसॉर्ट का उपयोग किया।
-=== जटिलता ===
-समानांतर कार्यान्वयन के लिए [[ बिग ओ अंकन ]] में दी गई जटिलता <math>p</math> प्रोसेसर:
+=== कम्प्लेक्सिटी ===
+<math>p</math> प्रोसेसर समानांतर कार्यान्वयन के लिए [[ बिग ओ अंकन |बिग ओ अंकन]] में दी गई कम्प्लेक्सिटी:
 स्प्लिटर्स खोजें.
 :<math>O\left(\frac{n}{p} + \log(p)\right)</math>
-बाल्टियों को भेजें.
+बकेट को भेजें.
-:<math>O(p)</math> सभी नोड्स को पढ़ने के लिए
+:<math>O(p)</math> सभी नोड्स को रीड करने के लिए
-:<math>O(\log(p))</math> प्रसारण के लिए
+:<math>O(\log(p))</math> ब्रॉड्कैस्टिंग के लिए
-:<math>O\left(\frac{n}{p} \log(p)\right)</math> सभी कुंजियों के लिए बाइनरी खोज के लिए
+:<math>O\left(\frac{n}{p} \log(p)\right)</math> सभी कीज के लिए बाइनरी सर्च हेतु
-:<math>O\left(\frac{n}{p}\right)</math> बकेट में चाबियाँ भेजने के लिए
+:<math>O\left(\frac{n}{p}\right)</math> बकेट में 'की' भेजने के लिए
-बाल्टियाँ क्रमबद्ध करें.
+बकेट को क्रमबद्ध करें.
-:<math>O\left(c\left(\frac{n}{p}\right) \right)</math> कहाँ <math>c(n)</math> अंतर्निहित अनुक्रमिक छँटाई पद्धति की जटिलता है।<ref name="sample_sort_tr.pdf" />अक्सर <math>c(n) = n \log(n)</math>.
+:<math>O\left(c\left(\frac{n}{p}\right) \right)</math> जहाँ <math>c(n)</math> अंतर्निहित अनुक्रमिक सॉर्टिंग पद्धति की कम्प्लेक्सिटी है।<ref name="sample_sort_tr.pdf" /> प्रायः <math>c(n) = n \log(n)</math>.
-इस एल्गोरिथम द्वारा की गई तुलनाओं की संख्या, सूचना सैद्धांतिक इष्टतम के करीब पहुंचती है <math>\log_2(n!)</math> बड़े इनपुट अनुक्रमों के लिए. फ़्रेज़र और मैककेलर द्वारा किए गए प्रयोगों में, एल्गोरिदम को क्विकॉर्ट की तुलना में 15% कम तुलना की आवश्यकता थी।
+इस एल्गोरिथम द्वारा की गई तुलनाओं की संख्या, सूचना सैद्धांतिक इष्टतम <math>\log_2(n!)</math> के निकट पहुंचती है  बड़े इनपुट अनुक्रमों के लिए. फ़्रेज़र और मैककेलर द्वारा किए गए प्रयोगों में, एल्गोरिदम को क्विकसॉर्ट की तुलना में 15% कम तुलना की आवश्यकता थी।
-== डेटा का नमूना लेना ==
+== डेटा सैंपलिंग ==
-डेटा का नमूना विभिन्न तरीकों से लिया जा सकता है। कुछ विधियों में शामिल हैं:
+डेटा का सैम्पल विभिन्न विधियों से लिया जा सकता है। कुछ विधियों में सम्मिलित हैं:
-# समान दूरी वाले नमूने चुनें.
+# समान दूरी वाले सैम्पल चुनें.
-# बेतरतीब ढंग से चयनित नमूने चुनें.
+# यादृच्छिक विधि से चयनित सैम्पल चुनें.
-=== [[ oversampling ]] ===
+=== [[ oversampling | ओवरसैंपलिंग]] ===
-ओवरसैंपलिंग अनुपात यह निर्धारित करता है कि स्प्लिटर्स को निर्धारित करने से पहले नमूने के रूप में कितनी बार अधिक डेटा तत्वों को खींचना है। लक्ष्य डेटा के वितरण का अच्छा प्रतिनिधित्व प्राप्त करना है। यदि डेटा मान व्यापक रूप से वितरित हैं, जिसमें कई डुप्लिकेट मान नहीं हैं, तो एक छोटा नमूना अनुपात पर्याप्त है। अन्य मामलों में जहां वितरण में कई डुप्लिकेट हैं, एक बड़ा ओवरसैंपलिंग अनुपात आवश्यक होगा। आदर्श स्थिति में, चरण 2 के बाद, प्रत्येक बाल्टी में शामिल होता है <math>n/p</math> तत्व. इस मामले में, किसी भी बाल्टी को सॉर्ट करने में अन्य की तुलना में अधिक समय नहीं लगता है, क्योंकि सभी बाल्टी समान आकार की होती हैं।
+ओवरसैंपलिंग अनुपात यह निर्धारित करता है कि स्प्लिटर्स को निर्धारित करने से पहले सैम्पल के रूप में कितनी बार अधिक डेटा एलमेंट को प्राप्त करना है। इसका लक्ष्य डेटा के वितरण का अच्छा प्रतिनिधित्व प्राप्त करना है। यदि डेटा मान व्यापक रूप से वितरित हैं, जिसमें कई डुप्लिकेट मान नहीं हैं, तो एक छोटा सैम्पल अनुपात पर्याप्त है। अन्य परिस्थितियों में जहां वितरण में कई डुप्लिकेट हैं, एक बड़ा ओवरसैंपलिंग अनुपात आवश्यक होगा। आदर्श स्थिति में, चरण 2 के उपरांत, प्रत्येक बकेट में <math>n/p</math> एलेमेन्ट सम्मिलित होता है। इस परिप्रेक्ष्य में, किसी भी बकेट को सॉर्ट करने में अन्य की तुलना में अधिक समय नहीं लगता है, क्योंकि सभी बकेट समान आकार के होतें हैं।
-खींचने के बाद <math>k</math> आवश्यकता से कई गुना अधिक नमूनों को क्रमबद्ध किया जाता है। इसके बाद, बाल्टी सीमाओं के रूप में उपयोग किए जाने वाले स्प्लिटर्स स्थिति में नमूने हैं <math>k, 2k, 3k, \dots, (p-1)k</math> नमूना अनुक्रम का (साथ में) <math>-\infty</math> और <math>\infty</math> क्रमशः सबसे बायीं और दायीं ओर की बाल्टियों के लिए बायीं और दायीं सीमाओं के रूप में)। यह केवल चयन करने की तुलना में अच्छे स्प्लिटर्स के लिए बेहतर अनुमान प्रदान करता है <math>p</math> बेतरतीब ढंग से विभाजित हो जाता है।
+आवश्यकता से '''<math>k</math>''' बार अधिक सैंपल निकालने के उपरांत, सैंपल सॉर्ट किया जाता है। इसके उपरांत, बकेट सीमाओं के रूप में उपयोग किए जाने वाले स्प्लिटर्स स्थिति में <math>k, 2k, 3k, \dots, (p-1)k</math> सैम्पल हैं। यह केवल चयन करने की तुलना में अच्छे स्प्लिटर्स के लिए उपयुक्त अनुमान प्रदान करता है तथा <math>p</math> यादृच्छिक विधि से विभाजित हो जाता है।
-=== बाल्टी आकार अनुमान ===
+=== बकेट आकार अनुमान ===
-परिणामी नमूना आकार के साथ, अपेक्षित बाल्टी आकार और विशेष रूप से एक निश्चित आकार से अधिक बाल्टी की संभावना का अनुमान लगाया जा सकता है। निम्नलिखित यह दिखाएगा कि ओवरसैंपलिंग कारक के लिए <math>S \in \Theta\left(\dfrac{\log n}{\epsilon^2}\right)</math> किसी भी बाल्टी में इससे अधिक न होने की प्रायिकता <math>(1 + \epsilon) \cdot \dfrac{n}{p}</math> तत्व से बड़ा है <math>1 - \dfrac{1}{n}</math>.
+परिणामी सैम्पल आकार के साथ, अपेक्षित बकेट आकार और विशेष रूप से एक निश्चित आकार से अधिक बकेट की संभावना का अनुमान लगाया जा सकता है। निम्नलिखित यह दिखाएगा कि ओवरसैंपलिंग कारक के लिए <math>S \in \Theta\left(\dfrac{\log n}{\epsilon^2}\right)</math> किसी भी बकेट में इससे अधिक न होने की प्रायिकता <math>(1 + \epsilon) \cdot \dfrac{n}{p}</math> <math>1 - \dfrac{1}{n}</math> एलमेंट से ज्यादा है।
-यह दिखाने के लिए चलो <math>\langle e_1, \dots, e_n\rangle</math> एक क्रमबद्ध अनुक्रम के रूप में इनपुट बनें। एक प्रोसेसर के लिए इससे अधिक प्राप्त करना <math>(1 + \epsilon) \cdot n/p</math> तत्वों, लंबाई के इनपुट का एक क्रम मौजूद होना चाहिए <math>(1 + \epsilon) \cdot n/p</math>, जिनमें से अधिकतम {{mvar|S}} नमूने उठाए गए हैं। ये मामले संभाव्यता का गठन करते हैं <math>P_\text{fail}</math>. इसे यादृच्छिक चर के रूप में दर्शाया जा सकता है:
+यह सिद्ध करने के लिए हम सॉर्टिड सीक्वन्स <math>\langle e_1, \dots, e_n\rangle</math> के रूप में इनपुट लेते हैं। प्रोसेसर को <math>(1 + \epsilon) \cdot n/p</math> से अधिक एलमेंट प्राप्त करने के लिए, <math>(1 + \epsilon) \cdot n/p</math> लंबाई का एक ऐसा उपसूत्र होना आवश्यक है, जिसमें से अधिकतम {{mvar|S}} सैंपल्स चुने जाते हैं। ये तथ्य <math>P_\text{fail}</math> संभाव्यता का गठन करते हैं। इसे यादृच्छिक चर के रूप में निम्नलिखित रूप से दर्शाया जा सकता है:
 <math display="block">X_i := \begin{cases}
 , & \text{if } s_i \in \left\langle e_j, \dots, e_j + (1 + \epsilon) \cdot \dfrac{n}{p}\right\rangle\\
@@ Line 75: / Line 86: @@
-== कई समान कुंजियाँ ==
-कई समान कुंजियों के मामले में, एल्गोरिदम कई पुनरावर्तन स्तरों से गुजरता है जहां अनुक्रमों को क्रमबद्ध किया जाता है, क्योंकि पूरे अनुक्रम में समान कुंजियाँ होती हैं। समानता बकेट शुरू करके इसका प्रतिकार किया जा सकता है। धुरी के बराबर तत्वों को उनके संबंधित समानता बकेट में क्रमबद्ध किया जाता है, जिसे केवल एक अतिरिक्त सशर्त शाखा के साथ कार्यान्वित किया जा सकता है। समानता की बाल्टियाँ आगे क्रमबद्ध नहीं हैं। यह काम करता है, क्योंकि कुंजियाँ अधिक से अधिक घटित होती हैं <math>n/k</math> समय के निर्णायक बनने की संभावना है।
-==समानांतर प्रणालियों में उपयोग ==
-[[File:Parallelersamplesort.svg|thumb|समानांतर सैम्पल सॉर्ट का उदाहरण <math>p=3</math> प्रोसेसर और एक ओवरसैंपलिंग कारक <math>k=3</math>.]]सैंपलसॉर्ट का उपयोग अक्सर समानांतर प्रणालियों में किया जाता है, जिसमें वितरित कंप्यूटिंग जैसे कि बल्क सिंक्रोनस समानांतर मशीनें शामिल हैं।<ref>{{cite journal |first1=Alexandros V. |last1=Gerbessiotis |first2=Leslie G. |last2=Valiant |title=डायरेक्ट बल्क-सिंक्रोनस समानांतर एल्गोरिदम|year=1992 |journal=J. Parallel and Distributed Computing |volume=22 |pages=22–251 |citeseerx=10.1.1.51.9332}}</ref><ref name="hill">{{cite journal |first1=Jonathan M. D. |last1=Hill |first2=Bill |last2=McColl |first3=Dan C. |last3=Stefanescu |first4=Mark W. |last4=Goudreau |first5=Kevin |last5=Lang |first6=Satish B. |last6=Rao |first7=Torsten |last7=Suel |first8=Thanasis |last8=Tsantilas |first9=Rob H. |last9=Bisseling |title=BSPlib: The BSP Programming Library |journal=Parallel Computing |volume=24 |issue=14 |year=1998 |pages=1947–1980 |citeseerx=10.1.1.48.1862|doi=10.1016/S0167-8191(98)00093-3 }}</ref><ref>{{cite conference |first1=William L. |last1=Hightower |first2=Jan F. |last2=Prins |first3=John H. |last3=Reif |year=1992 |title=बड़ी समानांतर मशीनों पर यादृच्छिक छँटाई का कार्यान्वयन|conference=ACM Symp. on Parallel Algorithms and Architectures |url=https://users.cs.duke.edu/~reif/paper/proteus/randsort.pdf}}</ref> स्प्लिटर्स की परिवर्तनीय मात्रा (क्विकसॉर्ट में केवल एक धुरी के विपरीत) के कारण, सैंपलसॉर्ट समानांतरीकरण और स्केलिंग के लिए बहुत उपयुक्त और सहज है। इसके अलावा सैंपलसॉर्ट भी उदाहरण के कार्यान्वयन की तुलना में अधिक कैश-कुशल है। जल्दी से सुलझाएं।
-प्रत्येक प्रोसेसर या नोड के लिए सॉर्टिंग को विभाजित करके समानांतरीकरण कार्यान्वित किया जाता है, जहां बकेट की संख्या प्रोसेसर की संख्या के बराबर होती है <math>p</math>. सैंपलसॉर्ट समानांतर सिस्टम में कुशल है क्योंकि प्रत्येक प्रोसेसर को लगभग समान बकेट आकार प्राप्त होता है <math>n/p</math>. चूँकि बकेट को समवर्ती रूप से क्रमबद्ध किया जाता है, प्रोसेसर लगभग एक ही समय में छंटाई को पूरा करेगा, इस प्रकार एक प्रोसेसर को दूसरों के लिए इंतजार नहीं करना पड़ेगा।
-वितरित सिस्टम पर, स्प्लिटर्स को लेकर चुना जाता है <math>k</math> प्रत्येक प्रोसेसर पर तत्व, परिणामी को सॉर्ट करना <math>kp</math> एक वितरित सॉर्टिंग एल्गोरिदम वाले तत्व, प्रत्येक को लेते हुए <math>k</math>-वें तत्व और परिणाम को सभी प्रोसेसरों पर प्रसारित करना। यह लागत है <math>T_\text{sort}(kp,p)</math> क्रमबद्ध करने के लिए <math>kp</math> तत्व चालू <math>p</math> प्रोसेसर, साथ ही  <math>T_\text{allgather}(p,p)</math> वितरित करने के लिए <math>p</math> के लिए स्प्लिटर्स को चुना <math>p</math> प्रोसेसर.
-परिणामी स्प्लिटर्स के साथ, प्रत्येक प्रोसेसर अपना इनपुट डेटा स्थानीय बकेट में रखता है। यह लेता है <math>\mathcal O(n/p\log p)</math> बाइनरी खोज के साथ. इसके बाद, स्थानीय बकेट को प्रोसेसरों में पुनः वितरित किया जाता है। प्रोसेसर <math>i</math> स्थानीय बाल्टियाँ मिलती हैं <math>b_i</math> अन्य सभी प्रोसेसरों का और इन्हें स्थानीय रूप से सॉर्ट करता है। वितरण लेता है <math>T_\text{all-to-all}(N, p)</math> समय, कहाँ <math>N</math> सबसे बड़ी बाल्टी का आकार है. स्थानीय छँटाई होती है <math>T_\text{localsort}(N)</math>.
-के दशक की शुरुआत में [[कनेक्शन मशीन]] सुपर कंप्यूटर पर किए गए प्रयोगों से पता चला कि सैंपल सॉर्ट इन मशीनों पर बड़े डेटासेट को सॉर्ट करने में विशेष रूप से अच्छा है, क्योंकि इसमें इंटरप्रोसेसर संचार ओवरहेड बहुत कम लगता है।<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> बाद के दिनों के [[जीपीजीपीयू]] पर, एल्गोरिदम इसके विकल्पों की तुलना में कम प्रभावी हो सकता है।<ref>{{cite conference |first1=Nadathur |last1=Satish |first2=Mark |last2=Harris |first3=Michael |last3=Garland |title=मैनीकोर जीपीयू के लिए कुशल सॉर्टिंग एल्गोरिदम डिजाइन करना|conference=Proc. IEEE Int'l Parallel and Distributed Processing Symp. |citeseerx=10.1.1.190.9846}}</ref>{{Citation needed|reason=The data are outdated in this paper since both GPU and CPU versions are much more efficient nowadays.|date=January 2018}}
-== सैम्पल सॉर्ट का कुशल कार्यान्वयन ==
-[[File:Animation.png|thumb|सुपर स्केलर सैंपलसॉर्ट का एनिमेटेड उदाहरण। प्रत्येक चरण में, जिन संख्याओं की तुलना की जाती है उन्हें नीले रंग से चिह्नित किया जाता है और जो संख्याएं अन्यथा पढ़ी या लिखी जाती हैं उन्हें लाल रंग से चिह्नित किया जाता है।]]जैसा कि ऊपर बताया गया है, सैंपलसॉर्ट एल्गोरिदम चयनित स्प्लिटर्स के अनुसार तत्वों को विभाजित करता है। पेपर सुपर स्केलर सैंपल सॉर्ट में एक कुशल कार्यान्वयन रणनीति प्रस्तावित है।<ref name=":0"/>पेपर में प्रस्तावित कार्यान्वयन आकार की दो सरणियों का उपयोग करता है <math>n</math> कुशल कार्यान्वयन के लिए (इनपुट डेटा युक्त मूल सरणी और एक अस्थायी)। इसलिए, कार्यान्वयन का यह संस्करण इन-प्लेस एल्गोरिदम नहीं है।
-प्रत्येक रिकर्सन चरण में, डेटा को विभाजित तरीके से अन्य सरणी में कॉपी किया जाता है। यदि डेटा अंतिम रिकर्सन चरण में अस्थायी सरणी में है, तो डेटा को मूल सरणी में वापस कॉपी किया जाता है।
-=== बाल्टियों का निर्धारण ===
-तुलना आधारित सॉर्टिंग एल्गोरिदम में तुलना ऑपरेशन सबसे महत्वपूर्ण प्रदर्शन हिस्सा है। सैंपलसॉर्ट में यह प्रत्येक तत्व के लिए बकेट निर्धारित करने से मेल खाता है। इसकी जरूरत है <math>\log k</math> प्रत्येक तत्व के लिए समय.
-सुपर स्केलर सैंपल सॉर्ट एक संतुलित खोज ट्री का उपयोग करता है जो एक सरणी में अंतर्निहित रूप से संग्रहीत होता है {{mvar|t}}. रूट को बाएँ उत्तराधिकारी 0 पर संग्रहीत किया जाता है <math>t_i</math> पर संग्रहित है <math>t_{2i}</math> और सही उत्तराधिकारी को यहां संग्रहीत किया जाता है <math>t_{2i+1}</math>. खोज वृक्ष दिया गया {{mvar|t}}, एल्गोरिदम बकेट संख्या की गणना करता है {{mvar|j}}तत्व का <math>a_i</math> इस प्रकार (मानते हुए) <math>a_i>t_j</math> यदि यह सत्य है तो 1 और अन्यथा 0 पर मूल्यांकन करता है):
-  जे := 1
+== कई इडेंटिकल 'की'(key) ==
-  लॉग दोहराएँ<sub>2</sub>(पी) बार
+कई इडेंटिकल 'की' के परिप्रेक्ष्य में, एल्गोरिदम कई पुनरावर्तन स्तरों से गुजरता है जहां अनुक्रमों को क्रमबद्ध किया जाता है, क्योंकि पूरे अनुक्रम में समान कुंजियाँ होती हैं। समानता बकेट प्रारंभ करके इसका प्रतिकार किया जा सकता है। पोल के बराबर एलमेंट को उनके संबंधित समानता बकेट में क्रमबद्ध किया जाता है, जिसे केवल एक अतिरिक्त सशर्त शाखा के साथ कार्यान्वित किया जा सकता है। समानता के बकेट आगे क्रमबद्ध नहीं हैं। यह काम करता है, क्योंकि कुंजियाँ अधिक से अधिक <math>n/k</math> घटित होती हैं। इसमे समय के निर्णायक बनने की संभावना है।
-      जे := 2जे + (ए > टी<sub>''j''</sub>)
-  जे := जे − पी + 1
+==पैरलेल सिस्टम में उपयोग ==
+[[File:Parallelersamplesort.svg|thumb|समानांतर सैम्पल सॉर्ट का उदाहरण <math>p=3</math> प्रोसेसर और एक ओवरसैंपलिंग कारक <math>k=3</math>.]]सैंपलसॉर्ट का उपयोग प्रायः पैरलेल सिस्टम में किया जाता है, जिसमें वितरित कंप्यूटिंग जैसे कि बल्क सिंक्रोनस पैरलेल मशीने सम्मिलित हैं।<ref>{{cite journal |first1=Alexandros V. |last1=Gerbessiotis |first2=Leslie G. |last2=Valiant |title=डायरेक्ट बल्क-सिंक्रोनस समानांतर एल्गोरिदम|year=1992 |journal=J. Parallel and Distributed Computing |volume=22 |pages=22–251 |citeseerx=10.1.1.51.9332}}</ref><ref name="hill">{{cite journal |first1=Jonathan M. D. |last1=Hill |first2=Bill |last2=McColl |first3=Dan C. |last3=Stefanescu |first4=Mark W. |last4=Goudreau |first5=Kevin |last5=Lang |first6=Satish B. |last6=Rao |first7=Torsten |last7=Suel |first8=Thanasis |last8=Tsantilas |first9=Rob H. |last9=Bisseling |title=BSPlib: The BSP Programming Library |journal=Parallel Computing |volume=24 |issue=14 |year=1998 |pages=1947–1980 |citeseerx=10.1.1.48.1862|doi=10.1016/S0167-8191(98)00093-3 }}</ref><ref>{{cite conference |first1=William L. |last1=Hightower |first2=Jan F. |last2=Prins |first3=John H. |last3=Reif |year=1992 |title=बड़ी समानांतर मशीनों पर यादृच्छिक छँटाई का कार्यान्वयन|conference=ACM Symp. on Parallel Algorithms and Architectures |url=https://users.cs.duke.edu/~reif/paper/proteus/randsort.pdf}}</ref> स्प्लिटर्स की परिवर्तनीय मात्रा (क्विकसॉर्ट में केवल एक पोल के विपरीत) के कारण, सैंपलसॉर्ट समानांतरीकरण और स्केलिंग के लिए बहुत उपयुक्त और सहज है। इसके अतिरिक्त सैंपलसॉर्ट भी उदाहरण के कार्यान्वयन की तुलना में अधिक कैश-एफीसिएंट है।
+पैरललीकरण को प्रत्येक प्रोसेसर या नोड के लिए विभाजित करके अंगीकृत किया जाता है, जहां बकेटों की संख्या प्रोसेसरों की संख्या <math>p</math> के बराबर होती है। सैंपलसॉर्ट पैरलल सिस्टम में प्रभावी होता है क्योंकि प्रत्येक प्रोसेसर को लगभग समान बकेट का आकार <math>n/p</math> प्राप्त होता है। बकेट समानांतर सॉर्ट किए जाते हैं, इसलिए प्रोसेसर लगभग समान समय में सॉर्टिंग पूरा कर जाते हैं, इससे किसी प्रोसेसर को दूसरों के लिए रुकने की आवश्यकता नहीं होती है।
+[[वितरित प्रणाली|वितरित सिस्टम]] पर, स्प्लिटर्स का चयन <math>k</math> एलमेंट को प्रत्येक प्रोसेसर पर लेकर किया जाता है, परिणामस्वरूप बने <math>kp</math> एलमेंट को वितरित सॉर्टिंग एल्गोरिदम के साथ सॉर्ट किया जाता है, हर <math>k</math>-वां तत्व चुना जाता है और परिणाम को सभी प्रोसेसरों को ब्रॉडकास्ट किया जाता है। यह <math>p</math> प्रोसेसरों पर <math>kp</math> एलमेंट को सॉर्ट करने के लिए <math>T_\text{sort}(kp,p)</math> का खर्च होता है, साथ ही <math>p</math> चुने गए स्प्लिटर्स को <math>p</math> प्रोसेसरों को वितरित करने के लिए <math>T_\text{allgather}(p,p)</math> का भी कॉस्ट होता है।
+परिणामकारी स्प्लिटर्स के साथ, प्रत्येक प्रोसेसर अपने इनपुट डेटा को स्थानीय बकेट में रखता है। इसके लिए [[बाइनरी खोज|बाइनरी सर्च]] के साथ <math>\mathcal O(n/p\log p)</math> का समय लगता है। इसके बाद, स्थानीय बकेट्स प्रोसेसरों को पुनः वितरित किए जाते हैं। प्रोसेसर <math>i</math> सभी अन्य प्रोसेसरों के स्थानीय बकेट्स <math>b_i</math> को प्राप्त करता है और इन्हें स्थानीय रूप से सॉर्ट करता है। वितरण <math>T_\text{all-to-all}(N, p)</math> समय लेता है, जहां <math>N</math> सबसे बड़े बकेट का आकार है। स्थानीय सॉर्ट <math>T_\text{localsort}(N)</math> का समय लेता है।
+के दशक में [[कनेक्शन मशीन]] सुपरकंप्यूटर पर किए गए प्रयोग ने दिखाया कि सैंपलसॉर्ट बड़े डेटासेट को सॉर्ट करने में विशेष रूप से अच्छा है, क्योंकि इसका इंटरप्रोसेसर संचार ओवरहेड कम होता है।<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>
+== सैम्पल सॉर्ट का एफीसिएंट कार्यान्वयन ==
+[[File:Animation.png|thumb|सुपर स्केलर सैंपलसॉर्ट का एनिमेटेड उदाहरण। प्रत्येक चरण में, जिन संख्याओं की तुलना की जाती है उन्हें नीले रंग से चिह्नित किया जाता है और जो संख्याएं अन्यथा रीड या राइट कीजाती हैं उन्हें लाल रंग से चिह्नित किया जाता है।]]जैसा कि ऊपर बताया गया है, सैंपलसॉर्ट एल्गोरिदम चयनित स्प्लिटर्स के अनुसार एलमेंट को विभाजित करता है। पेपर सुपर स्केलर सैंपल सॉर्ट में एक एफीसिएंट कार्यान्वयन रणनीति प्रस्तावित है।<ref name=":0"/>पेपर में प्रस्तावित कार्यान्वयन <math>n</math> एफीसिएंट कार्यान्वयन के लिए (इनपुट डेटा युक्त मूल ऐरे और एक अस्थायी) आकार की दो ऐरे का उपयोग करता है । इसलिए, कार्यान्वयन का यह संस्करण इन-प्लेस एल्गोरिदम नहीं है।
+प्रत्येक रिकर्सन चरण में, डेटा को डिवाइड विधि से अन्य ऐरे में कॉपी किया जाता है। यदि डेटा अंतिम रिकर्सन चरण में अस्थायी ऐरे में है, तो डेटा को मूल ऐरे में वापस कॉपी किया जाता है।
+=== बकेट का निर्धारण ===
+किसी तुलना-आधारित सॉर्टिंग एल्गोरिदम में तुलना की संचार ऑपरेशन सबसे प्रदर्शन-मुख्य भाग होती है। सैंपलसॉर्ट में यह तत्व के लिए बकेट निर्धारित करने के लिए होती है। इसमें प्रत्येक तत्व के लिए <math>\log k</math> समय लगता है।
+सुपर स्केलर सैंपल सॉर्ट एक बैलन्स सर्च ट्री का उपयोग करता है जो स्वतः में एक एरे {{mvar|t}} में रखा गया होता है। रूट ट्री 0 पर रखा जाता है, <math>t_i</math> का बाईं उत्तरधारी <math>t_{2i}</math> पर रखा जाता है और दाईं उत्तरधारी <math>t_{2i+1}</math> पर रखा जाता है। ट्री {{mvar|t}} को दिया गया है, एल्गोरिदम एलमेंट <math>a_i</math> का बकेट नंबर {{mvar|j}} निम्नलिखित विधि से निर्धारित करता है (यहां स्वीकृति है कि <math>a_i>t_j</math> का मूल्य 1 होगा यदि यह सत्य है और 0 होगा यदि यह सत्य नहीं है):
+  ''j'' := 1
+  repeat log<sub>2</sub>(''p'') times
+      ''j'' := 2''j'' + (''a'' > ''t''<sub>''j''</sub>)
+  ''j'' := ''j'' − ''p'' + 1
+बकेटों की संख्या {{mvar|k}} कंपाइल समय पर ज्ञात होती है, इसलिए कंपाइलर इस लूप को [[लूप अनरोलिंग|अनरोल कर]] सकता है। तुलना ऑपरेशन को [[प्रेडिकेशन (कंप्यूटर विज्ञान)|प्रेडिकेटेड इंस्ट्रक्शन्स]] के साथ लागू किया जाता है। इससे [[ब्रांच मिसप्रिडिक्शन]] नहीं होती है, जो तुलना ऑपरेशन को काफी धीमा बना सकता है।
-चूंकि बाल्टियों की संख्या {{mvar|k}} संकलन समय पर ज्ञात होता है, इस लूप को कंपाइलर द्वारा [[ लूप का खुलना ]] किया जा सकता है। तुलना ऑपरेशन प्रेडिकेशन (कंप्यूटर आर्किटेक्चर) के साथ कार्यान्वित किया जाता है। इस प्रकार, शाखा संबंधी कोई गलत पूर्वानुमान नहीं होता है, जिससे तुलनात्मक कार्रवाई काफी धीमी हो जाएगी।
 === विभाजन ===
-तत्वों के कुशल विभाजन के लिए, एल्गोरिदम को बकेट के आकार को पहले से जानने की आवश्यकता होती है। अनुक्रम के तत्वों को विभाजित करने और उन्हें सरणी में डालने के लिए, हमें बकेट का आकार पहले से जानना होगा। एक सरल एल्गोरिदम प्रत्येक बाल्टी के तत्वों की संख्या की गणना कर सकता है। फिर तत्वों को सही स्थान पर अन्य सरणी में डाला जा सकता है। इसका उपयोग करते हुए, प्रत्येक तत्व के लिए बाल्टी को दो बार निर्धारित करना होगा (एक बार बाल्टी में तत्वों की संख्या गिनने के लिए, और एक बार उन्हें डालने के लिए)।
+एक प्रभावशील विभाजन के लिए, एल्गोरिदम को अग्रिम बकेटों का आकार जानने की जरूरत होती है। अनुक्रम के एलमेंट को विभाजित करने और उन्हें एक एरे में रखने के लिए, हमें अग्रिम बकेटों के आकार को जानने की आवश्यकता होती है। एक साधारण एल्गोरिदम में हर बकेट के एलमेंट की संख्या को गिन सकता है। फिर एलमेंट को सही स्थान पर दूसरे एरे में डाला जा सकता है। इससे, हमें प्रत्येक तत्व के लिए दो बार बकेट का निर्धारण करने की आवश्यकता होगी (एक बार बकेट में एलमेंट की संख्या को गिनने के लिए और एक बार उन्हें इन्सर्ट करने के लिए)।
+इस दोहराने वाले तुलना को टालने के लिए, सुपर स्केलर सैंपल सॉर्ट एक अतिरिक्त एरे <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> बिट्स, ये लागत इनपुट सरणी के स्थान की तुलना में छोटी है।
 == इन-प्लेस सैंपलसॉर्ट ==
-ऊपर दिखाए गए कुशल सैंपलसॉर्ट कार्यान्वयन का एक मुख्य नुकसान यह है कि यह यथास्थान नहीं है और सॉर्टिंग के दौरान इनपुट अनुक्रम के समान आकार की दूसरी अस्थायी सरणी की आवश्यकता होती है। उदाहरण के लिए कुशल कार्यान्वयन क्विकसॉर्ट अपनी जगह पर हैं और इस प्रकार अधिक स्थान कुशल हैं। हालाँकि, सैंपलसॉर्ट को जगह-जगह भी लागू किया जा सकता है।<ref>{{cite journal|last1=Axtmann|first1=Michael|last2=Witt|first2=Sascha|last3=Ferizovic|first3=Daniel|last4=Sanders|first4=Peter|title=इन-प्लेस पैरेलल सुपर स्केलर सैंपलसॉर्ट (IPSSSSo)|journal=25th Annual European Symposium on Algorithms (ESA 2017)|date=2017|volume=87|issue=Leibniz International Proceedings in Informatics (LIPIcs)|pages=9:1–9:14|doi=10.4230/LIPIcs.ESA.2017.9}}</ref>
+ऊपर दिखाए गए एफीसिएंट सैंपलसॉर्ट कार्यान्वयन की एक मुख्य हानि यह है कि यह इन-प्लेस नहीं है और सॉर्टिंग के समय इनपुट अनुक्रम के समान आकार की दूसरी अस्थायी ऐरे की आवश्यकता होती है। उदाहरण के लिए एफीसिएंट कार्यान्वयन क्विकसॉर्ट इन-प्लेस हैं और इस प्रकार अधिक प्लेस एफीसिएंट हैं। यद्यपि, सैंपलसॉर्ट को इन-प्लेस पर भी लागू किया जा सकता है।<ref>{{cite journal|last1=Axtmann|first1=Michael|last2=Witt|first2=Sascha|last3=Ferizovic|first3=Daniel|last4=Sanders|first4=Peter|title=इन-प्लेस पैरेलल सुपर स्केलर सैंपलसॉर्ट (IPSSSSo)|journal=25th Annual European Symposium on Algorithms (ESA 2017)|date=2017|volume=87|issue=Leibniz International Proceedings in Informatics (LIPIcs)|pages=9:1–9:14|doi=10.4230/LIPIcs.ESA.2017.9}}</ref>
 इन-प्लेस एल्गोरिदम को चार चरणों में विभाजित किया गया है:
-# सैम्पलिंग जो उपरोक्त कुशल कार्यान्वयन में सैम्पलिंग के समतुल्य है।
+# सैम्पलिंग जो उपरोक्त एफीसिएंट कार्यान्वयन में सैम्पलिंग के समतुल्य है।
-# प्रत्येक प्रोसेसर पर स्थानीय वर्गीकरण, जो इनपुट को ब्लॉकों में समूहित करता है जैसे कि प्रत्येक ब्लॉक में सभी तत्व एक ही बकेट से संबंधित होते हैं, लेकिन बकेट आवश्यक रूप से मेमोरी में निरंतर नहीं होते हैं।
+# प्रत्येक प्रोसेसर पर स्थानीय वर्गीकरण, जो इनपुट को ब्लॉकों में समूहित करता है जैसे कि प्रत्येक ब्लॉक में सभी तत्व एक ही बकेट से संबंधित होते हैं, परंतु बकेट आवश्यक रूप से मेमोरी में निरंतर नहीं होते हैं।
 # ब्लॉक क्रमपरिवर्तन ब्लॉकों को विश्व स्तर पर सही क्रम में लाता है।
-# क्लीनअप कुछ तत्वों को बाल्टियों के किनारों पर ले जाता है।
+# क्लीनअप कुछ एलमेंट को बकेट के साइड पर ले जाता है।
-इस एल्गोरिदम का एक स्पष्ट नुकसान यह है कि यह प्रत्येक तत्व को दो बार पढ़ता और लिखता है, एक बार वर्गीकरण चरण में और एक बार ब्लॉक क्रमपरिवर्तन चरण में। हालाँकि, एल्गोरिथ्म अन्य अत्याधुनिक इन-प्लेस प्रतिस्पर्धियों की तुलना में तीन गुना तेज और अन्य अत्याधुनिक अनुक्रमिक प्रतिस्पर्धियों की तुलना में 1.5 गुना तेज प्रदर्शन करता है। जैसा कि नमूने के बारे में पहले ही ऊपर चर्चा की जा चुकी है, बाद के तीन चरणों के बारे में आगे विस्तार से बताया जाएगा।
+इस एल्गोरिदम की एक स्पष्ट हानि यह है कि यह प्रत्येक तत्व को दो बार रीड और राइट करता है, एक बार वर्गीकरण चरण में और एक बार ब्लॉक क्रमपरिवर्तन चरण में। यद्यपि, एल्गोरिथ्म अन्य अत्याधुनिक इन-प्लेस प्रतिस्पर्धियों की तुलना में तीन गुना तेज और अन्य अत्याधुनिक अनुक्रमिक प्रतिस्पर्धियों की तुलना में 1.5 गुना तेज प्रदर्शन करता है। जैसा कि सैम्पल के बारे में पहले ही ऊपर चर्चा की जा चुकी है, बाद के तीन चरणों के बारे में आगे विस्तार से बताया जाएगा।
 === स्थानीय वर्गीकरण ===
-पहले चरण में, इनपुट ऐरे को विभाजित किया गया है <math>p</math> समान आकार के ब्लॉकों की धारियाँ, प्रत्येक प्रोसेसर के लिए एक। प्रत्येक प्रोसेसर अतिरिक्त रूप से आवंटित करता है <math>k</math> बफ़र्स जो ब्लॉकों के समान आकार के होते हैं, प्रत्येक बाल्टी के लिए एक। इसके बाद, प्रत्येक प्रोसेसर अपनी पट्टी को स्कैन करता है और तत्वों को तदनुसार बाल्टी के बफर में ले जाता है। यदि कोई बफ़र भरा हुआ है, तो बफ़र सामने से शुरू करके, प्रोसेसर स्ट्राइप में लिखा जाता है। हमेशा खाली मेमोरी का कम से कम एक बफर आकार होता है, क्योंकि एक बफर को लिखने के लिए (यानी बफर भरा हुआ है), वापस लिखे गए तत्वों से अधिक तत्वों के कम से कम पूरे बफर आकार को स्कैन करना पड़ता है। इस प्रकार, प्रत्येक पूर्ण ब्लॉक में एक ही बाल्टी के तत्व होते हैं। स्कैन करते समय प्रत्येक बाल्टी के आकार पर नज़र रखी जाती है।
+पहले चरण में, इनपुट एरे को <math>p</math> समान आकार के ब्लॉकों के <math>p</math> स्ट्राइप्स में विभाजित किया जाता है, प्रत्येक प्रोसेसर के लिए एक। प्रत्येक प्रोसेसर अतिरिक्त रूप से <math>k</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>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> है, तो स्वैप बफर्स फिर से खाली हो जाते हैं। अन्यथा, स्वैप बफर्स में बचे रहे ब्लॉक को अपने गंतव्य बकेट में डालना अवश्यक होता है।
+यदि किसी प्रोसेसर की प्राथमिक बकेट की उपऐरे में सभी ब्लॉक सही बकेट में हैं, तो अगली बकेट को प्राथमिक बकेट के रूप में चुना जाता है। यदि कोई प्रोसेसर एक बार सभी बकेट को प्राथमिक बकेट के रूप में चुनता है, तो प्रोसेसर समाप्त हो जाता है।
+=== क्लीनअप ===
+चूँकि ब्लॉक क्रमपरिवर्तन चरण में केवल पूरे ब्लॉकों को स्थानांतरित किया गया था, कुछ तत्व अभी भी गलत विधि से बकेट सीमाओं के निकट रखे जा सकते हैं। चूंकि प्रत्येक तत्व के लिए ऐरे में पर्याप्त स्पेस होना चाहिए, उन गलत विधि से रखे गए एलमेंट को बाएं से दाएं खाली स्थानों पर ले जाया जा सकता है, अंत में ओवरफ्लो बफर पर विचार किया जा सकता है।
 == यह भी देखें ==
 * [[फ्लैशसॉर्ट]]
-* जल्दी से सुलझाएं
+* क्विकसॉर्ट
 ==संदर्भ==
@@ Line 152: / Line 229: @@
 {{sorting}}
-[[Category: छँटाई एल्गोरिदम]] [[Category: वितरित एल्गोरिदम]]
-[[Category: Machine Translated Page]]
+[[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]]
+[[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

Latest revision as of 13:52, 14 August 2023

एल्गोरिथम

स्यूडोकोड

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

डेटा सैंपलिंग

ओवरसैंपलिंग

बकेट आकार अनुमान

कई इडेंटिकल 'की'(key)

पैरलेल सिस्टम में उपयोग

सैम्पल सॉर्ट का एफीसिएंट कार्यान्वयन

बकेट का निर्धारण

विभाजन

इन-प्लेस सैंपलसॉर्ट

स्थानीय वर्गीकरण

ब्लॉक पर्म्यूटैशन

क्लीनअप

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories