Flashsort
फ्लैशसोर्ट एक वितरण छँटाई एल्गोरिथ्म है जो समान रूप से वितरित डेटा सेट और अपेक्षाकृत कम अतिरिक्त स्मृति आवश्यकता के लिए रैखिक कम्प्यूटेशनल जटिलता को दर्शाता है। मूल कार्य 1998 में कार्ल-डायट्रिच न्युबर्ट द्वारा प्रकाशित किया गया था। कॉन्सेप्ट फ्लैशसोर्ट हिस्टोग्राम सॉर्ट का एक कुशल इन-प्लेस कार्यान्वयन है, जो अपने आप में एक प्रकार का बाल्टी सॉर्ट है। यह प्रत्येक इनपुट तत्व को एक बाल्टी को सौंपता है, बाल्टी को सही क्रम में रखने के लिए इनपुट को कुशलता से पुनर्व्यवस्थित करता है, फिर प्रत्येक बाल्टी को क्रमबद्ध करता है। मूल एल्गोरिथ्म एक इनपुट सरणी को निम्नानुसार क्रमबद्ध करता हैः इनपुट या प्राथमिकता ज्ञान पर पहले पास का उपयोग करके, न्यूनतम और अधिकतम क्रमबद्ध कुंजी खोजें। रैखिक रूप से सीमा को बाल्टियों में विभाजित करें। प्रत्येक बाल्टी में आने वाले तत्वों की संख्या गिनते हुए, इनपुट के ऊपर से एक पास करें। (न्युबर्ट बाल्टियों को "वर्ग" और उनके बाल्टियों में तत्वों के असाइनमेंट को "वर्गीकरण" कहते हैं।) प्रत्येक बाल्टी में तत्वों की गिनती को उपसर्ग राशि में परिवर्तित करें, जहाँ बाल्टी में तत्वों की संख्या या उससे कम है। (और।) इनपुट को फिर से व्यवस्थित करें ताकि प्रत्येक बाल्टी के सभी तत्वों को उस स्थिति में संग्रहीत किया जा सके जहाँ। इनसर्शन सॉर्ट का उपयोग करके प्रत्येक बाल्टी को क्रमबद्ध करें। चरण 1-3 और 6 किसी भी बाल्टी प्रकार के लिए सामान्य हैं, और बाल्टी प्रकार के लिए सामान्य तकनीकों का उपयोग करके सुधार किया जा सकता है। विशेष रूप से, लक्ष्य बाल्टियों के लिए लगभग समान आकार (प्रत्येक तत्व) का होना है, जिसमें आदर्श मात्रा में विभाजित होना है। जबकि मूल एल्गोरिथ्म एक रैखिक प्रक्षेप क्रम है, यदि इनपुट वितरण को गैर-समान माना जाता है, तो एक गैर-रैखिक विभाजन इस आदर्श को अधिक निकटता से अनुमानित करेगा। इसी तरह, अंतिम सॉर्ट कई तकनीकों में से किसी का भी उपयोग कर सकता है, जिसमें एक पुनरावर्ती फ्लैश सॉर्ट भी शामिल है। जो बात फ़्लैश सॉर्ट को अलग करती है वह है चरण 5: केवल अतिरिक्त स्मृति के शब्दों का उपयोग करके प्रत्येक बाल्टी के तत्वों को सही सापेक्ष क्रम में एक साथ इकट्ठा करने के लिए एक कुशल इन-प्लेस एल्गोरिथ्म। स्मृति कुशल कार्यान्वयन फ्लैशसोर्ट पुनर्व्यवस्था चरण चक्रों में संचालित होता है। तत्व "अवर्गीकृत" से शुरू होते हैं, फिर उन्हें सही बाल्टी में ले जाया जाता है और "वर्गीकृत" माना जाता है। मूल प्रक्रिया एक अवर्गीकृत तत्व का चयन करना है, इसकी सही बाल्टी ढूंढना है, इसे एक अवर्गीकृत तत्व के साथ बदलना है (जो मौजूद होना चाहिए, क्योंकि हमने प्रत्येक बाल्टी के आकार को समय से पहले गिना है), इसे वर्गीकृत के रूप में चिह्नित करें, और फिर केवल बदले गए अवर्गीकृत तत्व के साथ दोहराएं। अंततः, तत्व का स्वयं के साथ आदान-प्रदान किया जाता है और चक्र समाप्त हो जाता है। प्रति बाल्टी दो (शब्द-आकार) चर का उपयोग करके विवरण को समझना आसान है। चतुराई का हिस्सा उन चरों में से एक का उन्मूलन है, जिससे दोगुनी बाल्टियों का उपयोग किया जा सकता है और इसलिए अंतिम छँटाई पर आधा समय बिताया जाता है। इसे प्रति बाल्टी दो चर के साथ समझने के लिए, मान लें कि अतिरिक्त शब्दों की दो सरणी हैंः बाल्टी (और) की (निश्चित) ऊपरी सीमा है, जबकि बाल्टी में एक (चल) सूचकांक है, इसलिए। हम लूप अपरिवर्तनीय बनाए रखते हैं कि प्रत्येक बाल्टी को एक अवर्गीकृत उपसर्ग (क्योंकि उन्हें अभी तक उनके लक्ष्य बाल्टी में स्थानांतरित नहीं किया गया है) और एक वर्गीकृत प्रत्यय (क्योंकि सभी सही बाल्टी में हैं और उन्हें फिर से स्थानांतरित नहीं किया जाएगा) में विभाजित किया जाता है। प्रारंभ में और सभी तत्व अवर्गीकृत हैं। जैसे-जैसे छँटाई आगे बढ़ती है, सभी तत्वों को तब तक घटाया जाता है जब तक कि सभी को सही बाल्टी में वर्गीकृत नहीं किया जाता है। प्रत्येक दौर पहली अपूर्ण रूप से वर्गीकृत बाल्टी (जिसमें है) खोजने और उस बाल्टी में पहला अवर्गीकृत तत्व लेने से शुरू होता है। (न्युबर्ट इसे "साइकिल लीडर" कहते हैं।) अस्थायी चर में प्रतिलिपि बनाएँ और दोहराएँः उस बाल्टी की गणना करें जो संबंधित है। मान लीजिए कि यह वह स्थान है जहाँ इसे रखा जाएगा। के साथ आदान-प्रदान, अर्थात। पिछले मूल्य को प्राप्त करते समय स्टोर करें जिससे विस्थापन होता है। इस तथ्य को प्रतिबिंबित करने के लिए गिरावट जिसे अब सही ढंग से वर्गीकृत किया गया है। यदि, तो इस लूप को नए के साथ फिर से शुरू करें। यदि, यह दौर समाप्त हो गया है और एक नया पहला अवर्गीकृत तत्व खोजें। जब कोई और अवर्गीकृत तत्व नहीं होते हैं, तो बाल्टियों में वितरण पूरा हो जाता है। जब इस तरह से प्रति बाल्टी दो चर के साथ लागू किया जाता है, तो प्रत्येक दौर के प्रारंभिक बिंदु का चयन वास्तव में मनमाना होता है; किसी भी अवर्गीकृत तत्व का उपयोग चक्र नेता के रूप में किया जा सकता है। एकमात्र आवश्यकता यह है कि साइकिल लीडर्स को कुशलता से पाया जा सके। यद्यपि पूर्ववर्ती विवरण चक्र नेताओं को खोजने के लिए उपयोग करता है, वास्तव में इसके बिना करना संभव है, जिससे पूरे-शब्द सरणी को समाप्त किया जा सकता है। (वितरण पूरा होने के बाद, बाल्टी की सीमाएँ पाई जा सकती हैं।) मान लीजिए कि हमने सभी तत्वों को वर्गीकृत किया है, और एक संभावित नए चक्र नेता के रूप में विचार कर रहे हैं। लक्ष्य की बाल्टी की गणना करना आसान है। लूप अपरिवर्तनीय द्वारा, इसे वर्गीकृत किया जाता है यदि, और अवर्गीकृत यदि उस सीमा के बाहर है। पहली असमानता का परीक्षण करना आसान है, लेकिन दूसरी के लिए मूल्य की आवश्यकता प्रतीत होती है। यह पता चला है कि प्रेरण परिकल्पना कि सभी तत्वों को वर्गीकृत किया गया है, इसका तात्पर्य है कि, इसलिए दूसरी असमानता का परीक्षण करना आवश्यक नहीं है। बाल्टी पर विचार करें कि वह किस स्थिति में आती है। वह है,। प्रेरण परिकल्पना के अनुसार, नीचे दिए गए सभी तत्व, जिनमें सभी बाल्टी शामिल हैं, पूरी तरह से वर्गीकृत हैं। आई. ई. उन बाल्टियों में शामिल कोई भी तत्व बाकी सरणी में नहीं रहता है। इसलिए यह संभव नहीं है। एकमात्र शेष मामला है, जिसका अर्थ है, क्यू. ई. डी.। इसे शामिल करते हुए, फ्लैशसोर्ट वितरण एल्गोरिथ्म ऊपर वर्णित और के साथ शुरू होता है। फिर आगे बढ़ेंः यदि वितरण पूरा हो गया है। यह देखते हुए, उस बाल्टी की गणना करें जिससे यह संबंधित है। यदि, तब अवर्गीकृत है। इसे एक अस्थायी चर की नकल करें औरः वह स्थान होने दें जहाँ इसे संग्रहीत किया जाएगा। के साथ आदान-प्रदान, अर्थात। पिछले मूल्य को प्राप्त करते समय स्टोर करें जिससे विस्थापन होता है। इस तथ्य को प्रतिबिंबित करने के लिए गिरावट जिसे अब सही ढंग से वर्गीकृत किया गया है। यदि, उस बाल्टी की गणना करें जिससे संबंधित है और इस (आंतरिक) लूप को नए के साथ फिर से शुरू करें। अब सही ढंग से वर्गीकृत किया गया है। (बाहरी) लूप को बढ़ाएँ और पुनः आरंभ करें। मेमोरी को बचाते समय, फ्लैशसोर्ट का नुकसान यह है कि यह पहले से ही वर्गीकृत कई तत्वों के लिए बाल्टी की पुनः गणना करता है। यह पहले से ही प्रति तत्व दो बार किया जाता है (एक बार बाल्टी-गिनती चरण के दौरान और दूसरी बार प्रत्येक तत्व को स्थानांतरित करते समय), लेकिन पहले अवर्गीकृत तत्व की खोज के लिए अधिकांश तत्वों के लिए तीसरी गणना की आवश्यकता होती है। यह महंगा हो सकता है यदि बाल्टियों को सरल रैखिक प्रक्षेप की तुलना में अधिक जटिल सूत्र का उपयोग करके सौंपा जाता है। एक प्रकार एक अधूरी बाल्टी में अंतिम अवर्गीकृत तत्व को साइकिल लीडर के रूप में लेकर गणनाओं की संख्या को लगभग कम कर देता हैः पहली अपूर्ण रूप से वर्गीकृत बाल्टी की पहचान करने के लिए एक चर बनाए रखें। शुरू करते हैं, और कब वितरण पूरा हो जाता है। जाने दीजिए। यदि, इस लूप को बढ़ाएँ और फिर से शुरू करें। (.) उस बाल्टी की गणना करें जो संबंधित है। अगर, तब और हम बाल्टी के साथ कर रहे हैं। इस लूप को बढ़ाएँ और पुनः आरंभ करें। यदि, वर्गीकरण तुच्छ है। इस लूप को घटाएँ और पुनः आरंभ करें। यदि, तब अवर्गीकृत है। पिछले मामले के समान वर्गीकरण लूप करें, फिर इस लूप को फिर से शुरू करें। अधिकांश तत्वों की बाल्टियों की गणना केवल दो बार की जाती है, सिवाय प्रत्येक बाल्टी के अंतिम तत्व के, जिसका उपयोग निम्नलिखित बाल्टी के पूरा होने का पता लगाने के लिए किया जाता है। एक छोटी सी और कमी अवर्गीकृत तत्वों की गिनती को बनाए रखते हुए और शून्य तक पहुंचने पर रोककर प्राप्त की जा सकती है। प्रदर्शन केवल अतिरिक्त स्मृति आवश्यकताएँ बाल्टी सीमा के भंडारण के लिए सहायक वेक्टर और उपयोग किए जाने वाले अन्य चरों की निरंतर संख्या हैं। इसके अलावा, प्रत्येक तत्व को केवल एक बार स्थानांतरित किया जाता है (एक अस्थायी बफर के माध्यम से, इसलिए दो चाल संचालन)। हालाँकि, यह स्मृति दक्षता इस नुकसान के साथ आती है कि सरणी को यादृच्छिक रूप से एक्सेस किया जाता है, इसलिए पूरे सरणी से छोटे डेटा कैश का लाभ नहीं उठा सकते हैं। सभी प्रकार की बाल्टियों की तरह, प्रदर्शन भी बाल्टियों के संतुलन पर निर्भर करता है। एक संतुलित डेटा सेट के आदर्श मामले में, प्रत्येक बाल्टी लगभग समान आकार की होगी। यदि इनपुट आकार में बाल्टियों की संख्या रैखिक है, तो प्रत्येक बाल्टी का एक स्थिर आकार होता है, इसलिए सम्मिलन सॉर्ट जैसे एल्गोरिदम के साथ एक बाल्टी को छांटने में जटिलता होती है। इसलिए अंतिम सम्मिलन प्रकारों का चलने का समय है। बाल्टियों की संख्या के लिए एक मूल्य चुनना, तत्वों (उच्च) को वर्गीकृत करने में बिताए गए समय और अंतिम सम्मिलन क्रमबद्ध चरण (निम्न) में बिताए गए समय का आदान-प्रदान करता है। उदाहरण के लिए, यदि आनुपातिक चुना जाता है, तो अंतिम सम्मिलन प्रकारों का चलने का समय है। सबसे खराब स्थिति में जहां लगभग सभी तत्व कुछ बाल्टियों में होते हैं, एल्गोरिथ्म की जटिलता अंतिम बाल्टी-छँटाई विधि के प्रदर्शन से सीमित होती है, इसलिए यह कम हो जाती है। एल्गोरिदम के परिवर्तन एक निश्चित आकार सीमा से अधिक बाल्टियों पर क्विकसोर्ट या रिकर्सिव फ्लैशसोर्ट जैसे बेहतर प्रदर्शन करने वाले प्रकारों का उपयोग करके सबसे खराब स्थिति में प्रदर्शन में सुधार करते हैं। समान रूप से वितरित यादृच्छिक डेटा के साथ, फ्लैशसोर्ट सभी के लिए हीपसोर्ट की तुलना में तेज और क्विकसोर्ट की तुलना में तेज है। यह क्विकसोर्ट से लगभग दोगुना तेज़ हो जाता है। ध्यान दें कि ये माप 1990 के दशक के अंत में लिए गए थे, जब स्मृति पदानुक्रम कैशिंग पर बहुत कम निर्भर थे। इन सीटू क्रमपरिवर्तन के कारण जो फ्लैशसोर्ट अपनी वर्गीकरण प्रक्रिया में प्रदर्शन करता है, फ्लैशसोर्ट स्थिर नहीं है। यदि स्थिरता की आवश्यकता है, तो दूसरी सरणी का उपयोग करना संभव है ताकि तत्वों को क्रमिक रूप से वर्गीकृत किया जा सके। हालांकि, इस मामले में, एल्गोरिथ्म को अतिरिक्त मेमोरी की आवश्यकता होगी। संदर्भों को छँटने के बजाय खोज के लिए वस्तुओं के वितरण का उपयोग करते हुए इंटरपोलेशन खोज भी देखें बाहरी लिंक बड़ी समानांतर मशीनों पर यादृच्छिक छँटाई का कार्यान्वयन (1992) समानांतर एल्गोरिदम का कार्यान्वयन (1992) फ्लैशसोर्ट छँटाई एल्गोरिदम का दृश्य