सैंपलसॉर्ट

सैंपलसॉर्ट एक छँटाई एल्गोरिथ्म है जो एक विभाजन और जीत एल्गोरिथ्म है जो अक्सर समानांतर प्रसंस्करण प्रणालियों में उपयोग किया जाता है। पारंपरिक विभाजन और जीत सॉर्टिंग एल्गोरिदम सरणी को उप-अंतराल या बकेट में विभाजित करता है। फिर बाल्टियों को अलग-अलग क्रमबद्ध किया जाता है और फिर एक साथ जोड़ दिया जाता है। हालाँकि, यदि सरणी को गैर-समान रूप से वितरित किया जाता है, तो इन सॉर्टिंग एल्गोरिदम का प्रदर्शन काफी हद तक कम हो सकता है। सैंपलसॉर्ट आकार का एक नमूना चुनकर इस समस्या का समाधान करता है s से n-तत्व अनुक्रम, और नमूने को क्रमबद्ध करके और चुनकर बाल्टियों की सीमा का निर्धारण करना p−1 < s परिणाम से तत्व। ये तत्व (जिन्हें स्प्लिटर्स कहा जाता है) फिर सरणी को विभाजित करते हैं p लगभग बराबर आकार की बाल्टियाँ। सैंपलसॉर्ट का वर्णन 1970 के पेपर, सैंपलसॉर्ट: ए सैंपलिंग अप्रोच टू मिनिमल स्टोरेज ट्री सॉर्टिंग में डब्ल्यू. डी. फ्रेज़र और ए. सी. मैककेलर द्वारा किया गया है।

एल्गोरिथम

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

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

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

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

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

स्यूडोकोड

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

फ़ंक्शन नमूनासॉर्ट(ए[1..एन], k, p)
    // यदि औसत बाल्टी का आकार सीमा से नीचे है तो उदाहरण के लिए स्विच करें। जल्दी से सुलझाएं
    यदि एन / के <थ्रेसहोल्ड तो स्मॉलसॉर्ट(ए)
    /* स्टेप 1 */
    एस = [एस चुनें1, ..., एस(p−1)k] यादृच्छिक रूप से // से नमूने चुनें
    क्रम से लगाना S // सॉर्ट नमूना
    [एस0, एस1, ..., एसp−1, एसp] <- [-∞, एसk, एस2k, ..., एस(p−1)k, ∞] // स्प्लिटर्स का चयन करें
    /* चरण दो */
    ए में प्रत्येक ए के लिए
        पाना j ऐसा कि एसj−1 <ए <= एसj

जगह a बाल्टी में बी_j /* चरण 3 और संयोजन */

    रिटर्न कॉन्टेनेट(नमूनासॉर्ट(बी1), ..., नमूना सॉर्ट (बीk))

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

जटिलता

समानांतर कार्यान्वयन के लिए बिग ओ अंकन में दी गई जटिलता $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)$ अंतर्निहित अनुक्रमिक छँटाई पद्धति की जटिलता है।अक्सर $c(n)=n\log(n)$.

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

डेटा का नमूना लेना

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

1. समान दूरी वाले नमूने चुनें.
2. बेतरतीब ढंग से चयनित नमूने चुनें.

oversampling

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

खींचने के बाद $k$ आवश्यकता से कई गुना अधिक नमूनों को क्रमबद्ध किया जाता है। इसके बाद, बाल्टी सीमाओं के रूप में उपयोग किए जाने वाले स्प्लिटर्स स्थिति में नमूने हैं $k,2k,3k,\dots ,(p-1)k$ नमूना अनुक्रम का (साथ में) $-\infty$ और $\infty$ क्रमशः सबसे बायीं और दायीं ओर की बाल्टियों के लिए बायीं और दायीं सीमाओं के रूप में)। यह केवल चयन करने की तुलना में अच्छे स्प्लिटर्स के लिए बेहतर अनुमान प्रदान करता है $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$$

कई समान कुंजियाँ

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

समानांतर प्रणालियों में उपयोग

समानांतर सैम्पल सॉर्ट का उदाहरण $p=3$ प्रोसेसर और एक ओवरसैंपलिंग कारक $k=3$.

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

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

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

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

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

सैम्पल सॉर्ट का कुशल कार्यान्वयन

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

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

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

बाल्टियों का निर्धारण

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

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

जे := 1
लॉग दोहराएँ2(पी) बार
    जे := 2जे + (ए > टीj)
जे := जे − पी + 1

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

विभाजन

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

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

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

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

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

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

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

पहले चरण में, इनपुट ऐरे को विभाजित किया गया है $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}$, स्वैप बफ़र्स फिर से खाली हैं। अन्यथा स्वैप बफ़र्स में बचे ब्लॉक को उसके गंतव्य बकेट में डालना होगा।

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

सफ़ाई

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

यह भी देखें

• फ्लैशसॉर्ट
• जल्दी से सुलझाएं

बाहरी संबंध

Frazer and McKellar's samplesort and derivatives:

• Frazer and McKellar's original paper
• DOI.org
• DOI.org

Adapted for use on parallel computers:

• http://citeseer.ist.psu.edu/91922.html
• http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.214