सैंपलसॉर्ट

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

एल्गोरिथम

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

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

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

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

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

स्यूडोकोड

निम्नलिखित सूची उपर्युक्त तीन चरण वाले एल्गोरिदम को स्यूडोकोड के रूप में प्रदर्शित करती है और दिखाती है कि एल्गोरिदम सिद्धांत रूप में कैसे कार्य करता है। निम्नांकित में, 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 = [S1, ..., S(p−1)k] randomly from // select samples
    sort S // sort sample
    [s0, s1, ..., sp−1, sp] <- [-∞, Sk, S2k, ..., S(p−1)k, ∞] // select splitters
    /* Step 2 */
    for each a in A
        find j such that sj−1 < a <= sj
        place a in bucket bj
    /* Step 3 and concatenation */
    return concatenate(sampleSort(b1), ..., sampleSort(bk))

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

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

$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. यादृच्छिक विधि से चयनित सैम्पल चुनें.

ओवरसैंपलिंग

ओवरसैंपलिंग अनुपात यह निर्धारित करता है कि स्प्लिटर्स को निर्धारित करने से पहले सैम्पल के रूप में कितनी बार अधिक डेटा एलमेंट को प्राप्त करना है। इसका लक्ष्य डेटा के वितरण का अच्छा प्रतिनिधित्व प्राप्त करना है। यदि डेटा मान व्यापक रूप से वितरित हैं, जिसमें कई डुप्लिकेट मान नहीं हैं, तो एक छोटा सैम्पल अनुपात पर्याप्त है। अन्य परिस्थितियों में जहां वितरण में कई डुप्लिकेट हैं, एक बड़ा ओवरसैंपलिंग अनुपात आवश्यक होगा। आदर्श स्थिति में, चरण 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$$