फ्लैशसॉर्ट: Difference between revisions

Revision as of 11:20, 14 July 2023

फ्लैशसॉर्ट एक वितरण सॉर्टिंग एल्गोरिदम है जो समान रूप से वितरित डेटा सेट और अपेक्षाकृत कम अतिरिक्त मेमोरी आवश्यकता के लिए रैखिक कम्प्यूटेशनल जटिलता $O (n)$ दिखाता है। मूल कार्य 1998 में कार्ल-डिट्रिच न्यूबर्ट द्वारा प्रकाशित किया गया था।^[1]

संकल्पना

फ्लैशसॉर्ट हिस्टोग्राम सॉर्ट का एक कुशल इन-प्लेस कार्यान्वयन है, जो स्वयं एक प्रकार का बकेट सॉर्ट है। यह प्रत्येक n इनपुट अवयव ों को m बकेट में से एक को निर्दिष्ट करता है, बकेट को सही क्रम में रखने के लिए इनपुट को कुशलतापूर्वक पुनर्व्यवस्थित करता है, फिर प्रत्येक बकेट को सॉर्ट करता है। मूल एल्गोरिदम एक इनपुट सरणी $A$ को निम्नानुसार सॉर्ट करता है:

इनपुट पर पहले पास या प्राथमिक ज्ञान का उपयोग करके न्यूनतम और अधिकतम सॉर्ट कुंजी खोजे ।
रेंज $[A min, A max]$ को रैखिक रूप से $m$ बकेट में विभाजित करें।
प्रत्येक बकेट में गिरने वाले $A i$ अवयव ों की संख्या गिनते हुए, इनपुट पर एक पास बनाते है। (न्यूबर्ट बकेट को "वर्ग" और उनकी बकेट में अवयव ों के असाइनमेंट को "वर्गीकरण" कहते हैं।)
प्रत्येक बकेट में अवयव ों की संख्या को उपसर्ग योग में बदलें, जहां $L b$ बकेट $b$ या उससे कम में अवयव ों $A i$ की संख्या है। (L0 = 0 और Lm = n.)
प्रत्येक बकेट b के सभी अवयव ों के इनपुट को पुनर्व्यवस्थित करें, स्थिति $A i$ में संग्रहीत किया जाता है जहां $L b -1 < i \leq L b$ ।
सम्मिलन सॉर्ट का उपयोग करके प्रत्येक बकेट को सॉर्ट करें।

चरण 1-3 और 6 किसी भी बकेट सॉर्ट के लिए सामान्य हैं, और बकेट सॉर्ट के लिए सामान्य तकनीकों का उपयोग करके इसमें सुधार किया जा सकता है। विशेष रूप से, लक्ष्य यह है कि बकेट लगभग समान आकार (प्रत्येक $n / m$ अवयव ) की हों^[1] जिसका आदर्श रूप m मात्राओं में विभाजन है। जबकि मूल एल्गोरिथ्म एक रैखिक प्रक्षेप प्रकार है, यदि इनपुट वितरण को गैर-समान माना जाता है, तो एक गैर-रेखीय विभाजन इस आदर्श को अधिक निकटता से अनुमानित करेगा। इसी तरह अंतिम सॉर्ट पुनरावर्ती फ़्लैश सॉर्ट सहित कई तकनीकों में से किसी एक का उपयोग कर सकता है।

फ़्लैश सॉर्ट को जो अलग करता है वह चरण 5 है: अतिरिक्त मेमोरी के केवल एम शब्दों का उपयोग करके प्रत्येक बकेट के अवयव ों को सही सापेक्ष क्रम में एकत्र करने के लिए एक कुशल $O (n)$ इन-प्लेस एल्गोरिदम है ।

मेमोरी कुशल कार्यान्वयन

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

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

प्रति बकेट दो चर के साथ इसे समझने के लिए, मान लें कि दो सारणियाँ हैं मान ले की $m$ अतिरिक्त शब्द: $K b$ बकेट की (निश्चित) ऊपरी सीमा है $b$ (और $K 0 = 0$ ), जबकि $L b$ बकेट $b$ में एक (चलने योग्य) सूचकांक है इसलिए $K b -1 \leq L b \leq K b$ .

हम लूप को अपरिवर्तनीय बनाए रखते हैं कि प्रत्येक बकेट को $L b$ द्वारा एक अवर्गीकृत उपसर्ग में विभाजित किया जाता है ( $K b -1 < i \leq L b$ के लिए $A i$ को अभी तक उनके लक्ष्य बकेट में स्थानांतरित नहीं किया गया है) और एक वर्गीकृत प्रत्यय ( $L b < i \leq K b$ के लिए $A i$ सभी हैं) सही बकेट में और दोबारा नहीं ले जाया जाएगा)। प्रारंभ में $L b = K b$ और सभी अवयव अवर्गीकृत हैं। जैसे-जैसे छँटाई आगे बढ़ती है, $L b$ को सभी $b$ के लिए $L b = K b -1$ तक घटाया जाता है और सभी अवयव ों को सही बकेट में वर्गीकृत किया जाता है।

प्रत्येक समय पहली अपूर्ण रूप से वर्गीकृत बकेट $c$ (जिसमें $K c -1 < L c$ है) को खोजने और उस बकेट $A i$ में पहला अवर्गीकृत अवयव लेने से प्रारंभ होता है जहां $i = K c -1 + 1$ है। (न्यूबर्ट इसे "साइकिल लीडर" कहते हैं।) $A i$ को अस्थायी चर t में प्रतिलिपि करें और दोहराएं:

उस बकेट b की गणना करें जिससे t संबंधित है।
मान लीजिए $j = L b$ वह स्थान है जहाँ t संग्रहीत किया जाएगा।
t को $A j$ के साथ बदलें, अथार्त पिछले मान $A j$ को प्राप्त करते समय t को $A j$ में संग्रहीत करें जिससे $A j$ विस्थापित हो जाए।
इस तथ्य को प्रतिबिंबित करने के लिए $L b$ घटाएं कि $A j$ को अब सही रूप से वर्गीकृत किया गया है।
यदि j ≠ i, तो इस लूप को नए t के साथ पुनरारंभ करें।
यदि j = i, तो यह दौर समाप्त हो गया है और एक नया पहला अवर्गीकृत अवयव $A i$ खोजे जाते है।
जब कोई अवर्गीकृत अवयव नहीं रह जाते हैं, तो बकेट में वितरण पूरा हो जाता है।

जब इस तरह से प्रति बकेट दो चर के साथ कार्यान्वित किया जाता है, तो प्रत्येक समय के प्रारंभिक बिंदु का विकल्प $i$ वास्तव में इच्छानुसार है; किसी भी अवर्गीकृत अवयव का उपयोग साइकिल लीडर के रूप में किया जा सकता है। एकमात्र आवश्यकता यह है कि साइकिल लीडरों को कुशलतापूर्वक पाया जा सकता है।

यद्यपि पिछला विवरण चक्र नेताओं को खोजने के लिए $K$ का उपयोग करता है, वास्तव में इसके बिना ऐसा करना संभव है, जिससे संपूर्ण $m$ -शब्द सरणी को समाप्त किया जा सकता है। (वितरण पूरा होने के बाद, बकेट सीमाएँ $L$ में पाई जा सकती हैं।)

मान लीजिए कि हमने $i -1$ तक के सभी अवयव ों को वर्गीकृत कर दिया है, और $A i$ को एक संभावित नए चक्र नेता के रूप में मान रहे हैं। इसके लक्ष्य बकेट $b$ की गणना करना आसान है। लूप इनवेरिएंट द्वारा, इसे वर्गीकृत किया जाता है यदि $L b < i \leq K b$ , और यदि $i$ उस सीमा से बाहर है तो अवर्गीकृत किया जाता है। पहली असमानता का परीक्षण करना आसान है, किंतु दूसरे के लिए मान $K b$ की आवश्यकता होती है।

यह पता चलता है कि प्रेरण परिकल्पना कि $i -1$ तक के सभी अवयव ों को वर्गीकृत किया गया है, इसका तात्पर्य है कि $i \leq K b$ , इसलिए दूसरी असमानता का परीक्षण करना आवश्यक नहीं है।

बकेट $c$ पर विचार करें जो $i$ स्थिति में आती है। अर्थात्, $K c -1 < i \leq K c$ . प्रेरण परिकल्पना के अनुसार, नीचे दिए गए सभी अवयव $i$ , जिसमें $K c -1 < i$ तक की सभी बकेट सम्मिलित हैं, पूरी तरह से वर्गीकृत हैं। अर्थात। उन बकेट में सम्मिलित कोई भी अवयव शेष सरणी में नहीं रहता है। इसलिए, यह संभव नहीं है कि $b < c$ .

एकमात्र शेष स्थिति b ≥ c है, जिसका अर्थ है $K b \geq K c \geq i$ , Q.E.D.

इसे सम्मिलित करते हुए, फ्लैशसॉर्ट वितरण एल्गोरिदम ऊपर बताए अनुसार $L$ से प्रारंभ होता है और $i = 1$ . फिर आगे बढ़ें:^[1]^[2]

यदि $i > n$ तो वितरण पूरा हो गया है।
$A i$ को देखते हुए, उस बकेट b की गणना करें जिससे वह संबंधित है।
यदि i ≤ L_b, तो A_i अवर्गीकृत है। इसे एक अस्थायी चर t प्रतिलिपि करें और:
- मान लीजिए $j = L b$ वह स्थान है जहाँ t संग्रहीत किया जाएगा।
- t को $A j$ के साथ बदलें, अर्थात पिछले मान $A j$ को प्राप्त करते समय t को $A j$ में संग्रहीत करें जिससे $A j$ विस्थापित हो जाए।
- इस तथ्य को प्रतिबिंबित करने के लिए $L b$ घटाएं कि $A j$ को अब सही रूप से वर्गीकृत किया गया है।
- यदि $j \neq i$ , तो उस बकेट $b$ की गणना करें जिससे t संबंधित है और इस (आंतरिक) लूप को नए $t$ के साथ पुनरारंभ करें।
$A i$ अब सही रूप से वर्गीकृत किया गया है। वेतन वृद्धि $i$ और (बाहरी) लूप को पुनरारंभ करें।

मेमोरी को सहेजते समय, फ्लैशसॉर्ट का हानि यह है कि यह पहले से ही वर्गीकृत कई अवयव के लिए बकेट की पुन: गणना करता है। यह पहले से ही प्रति अवयव दो बार किया जाता है (एक बार बकेट -गिनती चरण के समय और दूसरी बार प्रत्येक अवयव को स्थानांतरित करते समय), किंतु पहले अवर्गीकृत अवयव की खोज के लिए अधिकांश अवयव के लिए तीसरी गणना की आवश्यकता होती है। यह मूल्यवान हो सकता है यदि बकेट को सरल रैखिक प्रक्षेप की तुलना में अधिक जटिल सूत्र का उपयोग करके निर्दिष्ट किया जाता है। एक प्रकार चक्र लीडर के रूप में एक अधूरी बकेट में अंतिम अवर्गीकृत तत्व को लेकर गणनाओं की संख्या को लगभग $3 n$ से घटाकर अधिकतम $2 n + m - 1$ कर देता है:

पहले अपूर्ण-वर्गीकृत बकेट की पहचान करने वाला एक वेरिएबल c बनाए रखें। आरंभ करने के लिए मान लीजिए c = 1 है, और जब c > m वितरण पूरा हो जाता है।
चलो $i = L c$ . यदि $i = L c -1$ है, तो c बढ़ाएँ और इस लूप को पुनरारंभ करें। (L0 = 0.)
उस बकेट b की गणना करें जिससे $A i$ संबंधित है।
यदि b < c, तो $L c = K c -1$ और हमने बकेट c का काम पूरा कर लिया है। $c$ बढ़ाएँ और इस लूप को पुनरारंभ करें।
यदि b = c है, तो वर्गीकरण तुच्छ है। $L c$ घटाएं और इस लूप को पुनरारंभ करें।
यदि b > c, तो $A i$ अवर्गीकृत है। पिछले स्थिति की तरह ही वर्गीकरण लूप निष्पादित करें और फिर इस लूप को पुनरारंभ करें।

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

प्रदर्शन

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

सभी बकेट प्रकारों की तरह, प्रदर्शन गंभीर रूप से बकेट के संतुलन पर निर्भर करता है। संतुलित डेटा सेट के आदर्श स्थिति में, प्रत्येक बकेट लगभग समान आकार की होगी। यदि इनपुट आकार n में बकेट की संख्या $m$ रैखिक है, तो प्रत्येक बकेट का एक स्थिर आकार होता है, इसलिए एक एकल बकेट को $O (n 2)$ एल्गोरिदम जैसे प्रविष्टि सॉर्ट के साथ सॉर्ट करने में जटिलता $O (1 2) = O (1)$ होती है। इसलिए अंतिम प्रविष्टि प्रकार का चलने का समय $m \cdot O(1) = O (m) = O (n)$ है।

$m$ के लिए एक मान चुनना, बकेट की संख्या, तत्वों को वर्गीकृत करने में लगने वाला समय (उच्च $m$ ) और अंतिम प्रविष्टि सॉर्ट चरण (कम $m$ ) में लगने वाला समय कम हो जाता है। उदाहरण के लिए, यदि m को $\sqrt n$ के आनुपातिक रूप से चुना गया है, तो अंतिम प्रविष्टि प्रकार का चलने का समय $m \cdot O(\sqrt n 2) = O (n 3/2)$ है।

सबसे व्यर्थ स्थिति में जहां लगभग सभी तत्व कुछ बकेट में होते हैं, एल्गोरिदम की जटिलता अंतिम बकेट-सॉर्टिंग विधि के प्रदर्शन से सीमित होती है, इसलिए यह $O (n 2)$ तक घट जाती है। एल्गोरिदम की विविधताएं एक निश्चित आकार सीमा से अधिक की बकेट पर उत्तम प्रदर्शन करने वाले प्रकारों जैसे क्विकसॉर्ट या रिकर्सिव फ्लैशसॉर्ट का उपयोग करके सबसे व्यर्थ स्थिति के प्रदर्शन में सुधार करती हैं।।^[2]^[3]

समान रूप से वितरित यादृच्छिक डेटा के साथ $m = 0.1 n$ के लिए, फ्लैशसॉर्ट सभी $n$ के लिए हीप्सॉर्ट से तेज है और $n > 80$ के लिए क्विकॉर्ट से तेज है। यह $n = 10000$ पर क्विकॉर्ट से लगभग दोगुना तेज हो जाता है। ध्यान दें कि ये माप 1990 के दशक के अंत में लिए गए थे, जब मेमोरी पदानुक्रम कैशिंग पर बहुत कम निर्भर थे।

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

यह भी देखें

प्रक्षेप खोज, सॉर्टिंग के अतिरिक्त खोज के लिए वस्तुओं के वितरण का उपयोग करना

संदर्भ

↑ ^1.0 ^1.1 ^1.2 Neubert, Karl-Dietrich (February 1998). "फ्लैशसॉर्ट1 एल्गोरिथम". Dr. Dobb's Journal. 23 (2): 123–125, 131. Retrieved 2007-11-06.
↑ ^2.0 ^2.1 Neubert, Karl-Dietrich (1998). "फ्लैशसॉर्ट एल्गोरिथम". Retrieved 2007-11-06.
↑ Xiao, Li; Zhang, Xiaodong; Kubricht, Stefan A. (2000). "Improving Memory Performance of Sorting Algorithms: Cache-Effective Quicksort". ACM Journal of Experimental Algorithmics. 5. CiteSeerX 10.1.1.43.736. doi:10.1145/351827.384245. Archived from the original on 2007-11-02. Retrieved 2007-11-06.

बाहरी संबंध

[neubert_journal-1] 1.0 ^1.1 ^1.2 Neubert, Karl-Dietrich (February 1998). "फ्लैशसॉर्ट1 एल्गोरिथम". Dr. Dobb's Journal. 23 (2): 123–125, 131. Retrieved 2007-11-06.

[neubert_code-2] 2.0 ^2.1 Neubert, Karl-Dietrich (1998). "फ्लैशसॉर्ट एल्गोरिथम". Retrieved 2007-11-06.

[3] Xiao, Li; Zhang, Xiaodong; Kubricht, Stefan A. (2000). "Improving Memory Performance of Sorting Algorithms: Cache-Effective Quicksort". ACM Journal of Experimental Algorithmics. 5. CiteSeerX 10.1.1.43.736. doi:10.1145/351827.384245. Archived from the original on 2007-11-02. Retrieved 2007-11-06.

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
 {{short description|O(n) sorting algorithm}}
-फ्लैशसॉर्ट एक सॉर्टिंग एल्गोरिदम#डिस्ट्रीब्यूशन सॉर्ट्स एल्गोरिदम है जो ओ नोटेशन|रैखिक कम्प्यूटेशनल जटिलता दिखाता है {{mvar|''O''(''n'')}} समान रूप से वितरित डेटा सेट और अपेक्षाकृत कम अतिरिक्त मेमोरी आवश्यकता के लिए। मूल कार्य 1998 में कार्ल-डिट्रिच न्यूबर्ट द्वारा प्रकाशित किया गया था।<ref name="neubert_journal">{{cite journal |last=Neubert |first=Karl-Dietrich |date=February 1998 |title=फ्लैशसॉर्ट1 एल्गोरिथम|journal=Dr. Dobb's Journal |volume=23 |issue=2 |pages=123–125, 131 |url=http://www.ddj.com/architect/184410496 |access-date=2007-11-06}}</ref>
+फ्लैशसॉर्ट एक वितरण सॉर्टिंग एल्गोरिदम है जो समान रूप से वितरित डेटा सेट और अपेक्षाकृत कम अतिरिक्त मेमोरी आवश्यकता के लिए रैखिक कम्प्यूटेशनल जटिलता {{mvar|''O''(''n'')}} दिखाता है। मूल कार्य 1998 में कार्ल-डिट्रिच न्यूबर्ट द्वारा प्रकाशित किया गया था।<ref name="neubert_journal">{{cite journal |last=Neubert |first=Karl-Dietrich |date=February 1998 |title=फ्लैशसॉर्ट1 एल्गोरिथम|journal=Dr. Dobb's Journal |volume=23 |issue=2 |pages=123–125, 131 |url=http://www.ddj.com/architect/184410496 |access-date=2007-11-06}}</ref>
 == संकल्पना ==
-फ्लैशसॉर्ट हिस्टोग्राम सॉर्ट#हिस्टोग्राम सॉर्ट का एक कुशल [[ जगह में ]] कार्यान्वयन है, जो स्वयं एक प्रकार का [[ बाल्टी प्रकार ]] है। यह प्रत्येक को असाइन करता है {{mvar|n}} किसी एक में इनपुट तत्व {{mvar|m}} बकेट, बकेट को सही क्रम में रखने के लिए इनपुट को कुशलतापूर्वक पुनर्व्यवस्थित करता है, फिर प्रत्येक बकेट को क्रमबद्ध करता है। मूल एल्गोरिदम एक इनपुट सरणी को सॉर्ट करता है {{mvar|A}} निम्नलिखित नुसार:
+फ्लैशसॉर्ट हिस्टोग्राम सॉर्ट का एक कुशल इन-प्लेस कार्यान्वयन है, जो स्वयं एक प्रकार का बकेट सॉर्ट है। यह प्रत्येक n इनपुट अवयव ों को m बकेट में से एक को निर्दिष्ट करता है, बकेट को सही क्रम में रखने के लिए इनपुट को कुशलतापूर्वक पुनर्व्यवस्थित करता है, फिर प्रत्येक बकेट को सॉर्ट करता है। मूल एल्गोरिदम एक इनपुट सरणी {{mvar|A}} को निम्नानुसार सॉर्ट करता है:
-# इनपुट पर पहले पास या प्राथमिक ज्ञान का उपयोग करके, न्यूनतम और अधिकतम सॉर्ट कुंजी ढूंढें।
+#इनपुट पर पहले पास या प्राथमिक ज्ञान का उपयोग करके न्यूनतम और अधिकतम सॉर्ट कुंजी खोजे ।
-# रेंज को रैखिक रूप से विभाजित करें {{math|[''A''<sub>min</sub>, ''A''<sub>max</sub>]}} में {{mvar|m}} बाल्टियाँ।
+#रेंज {{math|[''A''<sub>min</sub>, ''A''<sub>max</sub>]}} को रैखिक रूप से {{mvar|m}} बकेट में विभाजित करें।
-# तत्वों की संख्या गिनते हुए, इनपुट पर एक पास बनाएं {{mvar|A<sub>i</sub>}} जो प्रत्येक बाल्टी में गिरती है। (न्यूबर्ट बकेट क्लासेस और तत्वों के असाइनमेंट को उनके बकेट वर्गीकरण कहते हैं।)
+#प्रत्येक बकेट में गिरने वाले {{mvar|A<sub>i</sub>}} अवयव ों की संख्या गिनते हुए, इनपुट पर एक पास बनाते है। (न्यूबर्ट बकेट को "वर्ग" और उनकी बकेट में अवयव ों के असाइनमेंट को "वर्गीकरण" कहते हैं।)
-# प्रत्येक बकेट में तत्वों की संख्या को [[उपसर्ग योग]] में बदलें, जहां {{mvar|L<sub>b</sub>}}तत्वों की संख्या है {{mvar|A<sub>i</sub>}} बाल्टी में {{mvar|b}} या कम। ({{math|1=''L''<sub>0</sub> = 0}} और {{math|1=''L<sub>m</sub>'' = ''n''}}.)
+#प्रत्येक बकेट में अवयव ों की संख्या को उपसर्ग योग में बदलें, जहां {{mvar|L<sub>b</sub>}} बकेट {{mvar|b}} या उससे कम में अवयव ों {{mvar|A<sub>i</sub>}} की संख्या है। (L0 = 0 और Lm = n.)
-# प्रत्येक बकेट के सभी तत्वों में इनपुट को पुनर्व्यवस्थित करें {{mvar|b}} पदों पर संग्रहीत हैं {{mvar|A<sub>i</sub>}} कहाँ {{math|''L''<sub>''b''&minus;1</sub> &lt; ''i'' ≤ ''L<sub>b</sub>''}}.
+#प्रत्येक बकेट b के सभी अवयव ों के इनपुट को पुनर्व्यवस्थित करें, स्थिति {{mvar|A<sub>i</sub>}} में संग्रहीत किया जाता है जहां {{math|''L''<sub>''b''&minus;1</sub> &lt; ''i'' ≤ ''L<sub>b</sub>''}}।
 # [[ सम्मिलन सॉर्ट ]] का उपयोग करके प्रत्येक बकेट को सॉर्ट करें।
-चरण 1-3 और 6 किसी भी बकेट सॉर्ट के लिए सामान्य हैं, और बकेट सॉर्ट के लिए सामान्य तकनीकों का उपयोग करके इसमें सुधार किया जा सकता है। विशेष रूप से, लक्ष्य यह है कि बाल्टियाँ लगभग समान आकार की हों ({{math|''n''/''m''}}तत्व प्रत्येक),<ref name="neubert_journal" />  आदर्श विभाजन के साथ {{mvar|m}} मात्राएँ। जबकि मूल एल्गोरिथ्म एक रैखिक प्रक्षेप प्रकार है, यदि इनपुट संभाव्यता वितरण को गैर-समान माना जाता है, तो एक गैर-रेखीय विभाजन इस आदर्श को अधिक निकटता से अनुमानित करेगा। इसी तरह, अंतिम सॉर्ट पुनरावर्ती फ़्लैश सॉर्ट सहित कई तकनीकों में से किसी एक का उपयोग कर सकता है।
+चरण 1-3 और 6 किसी भी बकेट सॉर्ट के लिए सामान्य हैं, और बकेट सॉर्ट के लिए सामान्य तकनीकों का उपयोग करके इसमें सुधार किया जा सकता है। विशेष रूप से, लक्ष्य यह है कि बकेट लगभग समान आकार (प्रत्येक{{math|''n''/''m''}} अवयव ) की हों<ref name="neubert_journal" /> जिसका आदर्श रूप m मात्राओं में विभाजन है। जबकि मूल एल्गोरिथ्म एक रैखिक प्रक्षेप प्रकार है, यदि इनपुट वितरण को गैर-समान माना जाता है, तो एक गैर-रेखीय विभाजन इस आदर्श को अधिक निकटता से अनुमानित करेगा। इसी तरह अंतिम सॉर्ट पुनरावर्ती फ़्लैश सॉर्ट सहित कई तकनीकों में से किसी एक का उपयोग कर सकता है।
-फ़्लैश सॉर्ट को जो अलग करता है वह चरण 5 है: एक कुशल {{math|''O''(''n'')}} केवल उपयोग करके प्रत्येक बकेट के तत्वों को सही सापेक्ष क्रम में एकत्रित करने के लिए इन-प्लेस एल्गोरिदम {{mvar|m}}अतिरिक्त मेमोरी के शब्द.
+फ़्लैश सॉर्ट को जो अलग करता है वह चरण 5 है: अतिरिक्त मेमोरी के केवल एम शब्दों का उपयोग करके प्रत्येक बकेट के अवयव ों को सही सापेक्ष क्रम में एकत्र करने के लिए एक कुशल {{math|''O''(''n'')}}  इन-प्लेस एल्गोरिदम है ।
 == मेमोरी कुशल कार्यान्वयन ==
-फ्लैशसॉर्ट पुनर्व्यवस्था चरण चक्रों और निश्चित बिंदुओं में संचालित होता है। तत्व अवर्गीकृत से शुरू होते हैं, फिर सही बकेट में ले जाए जाते हैं और वर्गीकृत माने जाते हैं। मूल प्रक्रिया एक अवर्गीकृत तत्व को चुनना, उसकी सही बाल्टी ढूंढना, उसे वहां एक अवर्गीकृत तत्व के साथ विनिमय करना है (जो अस्तित्व में होना चाहिए, क्योंकि हमने प्रत्येक बाल्टी के आकार को समय से पहले गिना है), इसे वर्गीकृत के रूप में चिह्नित करें, और फिर उसी के साथ दोहराएं। अभी-अभी अवर्गीकृत तत्व का आदान-प्रदान किया गया। अंततः, तत्व का आपस में आदान-प्रदान हो जाता है और चक्र समाप्त हो जाता है।
+फ्लैशसॉर्ट पुनर्व्यवस्था चरण चक्रों और निश्चित बिंदुओं में संचालित होता है। अवयव  "अवर्गीकृत" से प्रारंभ होते हैं फिर उन्हें सही बकेट में ले जाया जाता है और "वर्गीकृत" माना जाता है। मूल प्रक्रिया एक अवर्गीकृत अवयव  को चुनना, उसकी सही बकेट खोजा जाता है, उसे वहां एक अवर्गीकृत अवयव  के साथ विनिमय करना है (जो अस्तित्व में होना चाहिए, क्योंकि हमने प्रत्येक बकेट के आकार को समय से पहले गिना है), इसे वर्गीकृत के रूप में चिह्नित करें, और फिर उसी के साथ दोहराएं। अभी-अभी अवर्गीकृत अवयव  का आदान-प्रदान किया गया था। अंततः, अवयव  का आपस में आदान-प्रदान हो जाता है और चक्र समाप्त हो जाता है।
-प्रति बाल्टी दो (शब्द-आकार) चर का उपयोग करके विवरण को समझना आसान है। चतुर हिस्सा उन चरों में से एक को खत्म करना है, जिससे दोगुनी बाल्टियों का उपयोग किया जा सकता है और इसलिए अंतिम पर आधा समय खर्च किया जा सकता है। {{math|''O''(''n''<sup>2</sup>)}} छंटाई.
+प्रति बकेट दो (शब्द-आकार) चर का उपयोग करके विवरण को समझना आसान है। चतुर भाग उन चरों में से एक को समाप्त करना है, जिससे दोगुनी बकेट का उपयोग किया जा सकता है और इसलिए अंतिम {{math|''O''(''n''<sup>2</sup>)}} सॉर्टिंग पर आधा समय खर्च किया जाता है।
-प्रति बाल्टी दो चर के साथ इसे समझने के लिए, मान लें कि दो सारणियाँ हैं {{mvar|m}}अतिरिक्त शब्द: {{mvar|K<sub>b</sub>}} बाल्टी की (निश्चित) ऊपरी सीमा है {{mvar|b}} (और {{math|1=''K''<sub>0</sub> = 0}}), जबकि {{mvar|L<sub>b</sub>}} बकेट में एक (चलने योग्य) सूचकांक है {{mvar|b}}, इसलिए {{math|''K''<sub>''b''&minus;1</sub> ≤ ''L<sub>b</sub>'' ≤ ''K<sub>b</sub>''}}.
+प्रति बकेट दो चर के साथ इसे समझने के लिए, मान लें कि दो सारणियाँ हैं मान ले की {{mvar|m}} अतिरिक्त शब्द: {{mvar|K<sub>b</sub>}} बकेट की (निश्चित) ऊपरी सीमा है {{mvar|b}} (और {{math|1=''K''<sub>0</sub> = 0}}), जबकि {{mvar|L<sub>b</sub>}} बकेट {{mvar|b}} में एक (चलने योग्य) सूचकांक है इसलिए {{math|''K''<sub>''b''&minus;1</sub> ≤ ''L<sub>b</sub>'' ≤ ''K<sub>b</sub>''}}.
-हम लूप को अपरिवर्तनीय बनाए रखते हैं जिससे प्रत्येक बाल्टी विभाजित होती है {{mvar|L<sub>b</sub>}} एक अवर्गीकृत उपसर्ग में ({{mvar|A<sub>i</sub>}} के लिए {{math|''K''<sub>''b''&minus;1</sub> &lt; ''i'' ≤ ''L<sub>b</sub>''}} को अभी तक उनके लक्ष्य बकेट में ले जाया जाना बाकी है) और एक वर्गीकृत प्रत्यय ({{mvar|A<sub>i</sub>}} के लिए {{math|''L<sub>b</sub>'' &lt; ''i'' ≤ ''K<sub>b</sub>''}} सभी सही बकेट में हैं और इन्हें दोबारा स्थानांतरित नहीं किया जाएगा)। शुरू में {{math|1=''L<sub>b</sub>'' = ''K<sub>b</sub>''}} और सभी तत्व अवर्गीकृत हैं। जैसे-जैसे छँटाई आगे बढ़ती है, {{mvar|L<sub>b</sub>}} तक घटे हैं {{math|1=''L<sub>b</sub>'' = ''K''<sub>''b''&minus;1</sub>}} सभी के लिए {{mvar|b}} और सभी तत्वों को सही बकेट में वर्गीकृत किया गया है।
+हम लूप को अपरिवर्तनीय बनाए रखते हैं कि प्रत्येक बकेट को {{mvar|L<sub>b</sub>}}  द्वारा एक अवर्गीकृत उपसर्ग में विभाजित किया जाता है ({{math|''K''<sub>''b''&minus;1</sub> &lt; ''i'' ≤ ''L<sub>b</sub>''}} के लिए {{mvar|A<sub>i</sub>}} को अभी तक उनके लक्ष्य बकेट में स्थानांतरित नहीं किया गया है) और एक वर्गीकृत प्रत्यय ({{math|''L<sub>b</sub>'' &lt; ''i'' ≤ ''K<sub>b</sub>''}} के लिए {{mvar|A<sub>i</sub>}} सभी हैं) सही बकेट में और दोबारा नहीं ले जाया जाएगा)। प्रारंभ में {{math|1=''L<sub>b</sub>'' = ''K<sub>b</sub>''}} और सभी अवयव  अवर्गीकृत हैं। जैसे-जैसे छँटाई आगे बढ़ती है,{{mvar|L<sub>b</sub>}} को सभी {{mvar|b}} के लिए {{math|1=''L<sub>b</sub>'' = ''K''<sub>''b''&minus;1</sub>}} तक घटाया जाता है और सभी अवयव ों को सही बकेट में वर्गीकृत किया जाता है।
-प्रत्येक दौर की शुरुआत पहली अपूर्ण रूप से वर्गीकृत बाल्टी को खोजने से होती है {{mvar|c}} (जो है {{math|''K''<sub>''c''&minus;1</sub> &lt; ''L<sub>c</sub>''}}) और उस बकेट में पहला अवर्गीकृत तत्व लेना {{mvar|A<sub>i</sub>}} कहाँ {{math|1=''i'' = ''K''<sub>''c''&minus;1</sub> + 1}}. (न्यूबर्ट इसे साइकिल लीडर कहते हैं।) प्रतिलिपि {{mvar|A<sub>i</sub>}} एक अस्थायी चर के लिए {{mvar|t}} और दोहराओ:
+प्रत्येक समय पहली अपूर्ण रूप से वर्गीकृत बकेट {{mvar|c}} (जिसमें {{math|''K''<sub>''c''&minus;1</sub> &lt; ''L<sub>c</sub>''}} है) को खोजने और उस बकेट {{mvar|A<sub>i</sub>}} में पहला अवर्गीकृत अवयव  लेने से प्रारंभ होता है जहां {{math|1=''i'' = ''K''<sub>''c''&minus;1</sub> + 1}} है। (न्यूबर्ट इसे "साइकिल लीडर" कहते हैं।) {{mvar|A<sub>i</sub>}} को अस्थायी चर t में प्रतिलिपि करें और दोहराएं:
-* बाल्टी की गणना करें {{mvar|b}} किसको {{mvar|t}} का है.
+* उस बकेट b की गणना करें जिससे t संबंधित है।
-* होने देना {{math|1=''j'' = ''L<sub>b</sub>''}} वह स्थान हो जहां {{mvar|t}} संग्रहित किया जाएगा.
+*मान लीजिए {{math|1=''j'' = ''L<sub>b</sub>''}} वह स्थान है जहाँ t संग्रहीत किया जाएगा।
-* अदला-बदली {{mvar|t}} साथ {{mvar|A<sub>j</sub>}}, अर्थात। इकट्ठा करना {{mvar|t}} में {{mvar|A<sub>j</sub>}} पिछला मान लाते समय {{mvar|A<sub>j</sub>}} जिससे विस्थापित हो गया।
+*t को {{mvar|A<sub>j</sub>}} के साथ बदलें, अथार्त पिछले मान {{mvar|A<sub>j</sub>}} को प्राप्त करते समय t को {{mvar|A<sub>j</sub>}} में संग्रहीत करें जिससे {{mvar|A<sub>j</sub>}} विस्थापित हो जाए।
-*घटना {{mvar|L<sub>b</sub>}} इस तथ्य को प्रतिबिंबित करने के लिए {{mvar|A<sub>j</sub>}} अब सही ढंग से वर्गीकृत किया गया है।
+*इस तथ्य को प्रतिबिंबित करने के लिए {{mvar|L<sub>b</sub>}} घटाएं कि {{mvar|A<sub>j</sub>}} को अब सही रूप  से वर्गीकृत किया गया है।
-* अगर {{math|''j'' ≠ ''i''}}, इस लूप को नए के साथ पुनरारंभ करें {{mvar|t}}.
+*यदि j ≠ i, तो इस लूप को नए t के साथ पुनरारंभ करें।
-* अगर {{math|1=''j'' = ''i''}}, यह दौर समाप्त हो गया है और एक नया पहला अवर्गीकृत तत्व ढूंढें {{mvar|A<sub>i</sub>}}.
+*यदि j = i, तो यह दौर समाप्त हो गया है और एक नया पहला अवर्गीकृत अवयव  {{mvar|A<sub>i</sub>}} खोजे जाते है।
-* जब कोई अवर्गीकृत तत्व नहीं रह जाते हैं, तो बाल्टियों में वितरण पूरा हो जाता है।
+* जब कोई अवर्गीकृत अवयव  नहीं रह जाते हैं, तो बकेट में वितरण पूरा हो जाता है।
-जब इस तरह से प्रति बाल्टी दो चर के साथ कार्यान्वित किया जाता है, तो प्रत्येक दौर के शुरुआती बिंदु का विकल्प {{mvar|i}} वास्तव में मनमाना है; किसी भी अवर्गीकृत तत्व का उपयोग साइकिल लीडर के रूप में किया जा सकता है। एकमात्र आवश्यकता यह है कि साइकिल लीडरों को कुशलतापूर्वक पाया जा सके।
+जब इस तरह से प्रति बकेट दो चर के साथ कार्यान्वित किया जाता है, तो प्रत्येक समय के प्रारंभिक बिंदु का विकल्प {{mvar|i}} वास्तव में इच्छानुसार है; किसी भी अवर्गीकृत अवयव  का उपयोग साइकिल लीडर के रूप में किया जा सकता है। एकमात्र आवश्यकता यह है कि साइकिल लीडरों को कुशलतापूर्वक पाया जा सकता है।
-हालाँकि पूर्ववर्ती विवरण का उपयोग करता है {{mvar|K}} चक्र के नेताओं को खोजने के लिए, वास्तव में इसके बिना करना संभव है, संपूर्ण को अनुमति देना {{mvar|m}}-शब्द सारणी को हटाया जाना है। (वितरण पूरा होने के बाद, बकेट सीमाएँ पाई जा सकती हैं {{mvar|L}}.)
+यद्यपि पिछला विवरण चक्र नेताओं को खोजने के लिए {{mvar|K}} का उपयोग करता है, वास्तव में इसके बिना ऐसा करना संभव है, जिससे संपूर्ण {{mvar|m}}-शब्द सरणी को समाप्त किया जा सकता है। (वितरण पूरा होने के बाद, बकेट सीमाएँ {{mvar|L}} में पाई जा सकती हैं।)
-मान लीजिए कि हमने सभी तत्वों को वर्गीकृत कर दिया है {{math|''i''&minus;1}}, और विचार कर रहे हैं {{mvar|A<sub>i</sub>}} एक संभावित नए साइकिल नेता के रूप में। इसके लक्ष्य बकेट की गणना करना आसान है {{mvar|b}}. लूप इनवेरिएंट द्वारा, इसे वर्गीकृत किया गया है {{math|''L<sub>b</sub>'' &lt; ''i'' ≤ ''K<sub>b</sub>''}}, और अवर्गीकृत यदि {{mvar|i}} उस सीमा से बाहर है. पहली [[असमानता (गणित)]] का परीक्षण करना आसान है, लेकिन दूसरे के लिए मूल्य की आवश्यकता होती है {{mvar|K<sub>b</sub>}}.
+मान लीजिए कि हमने {{math|''i''&minus;1}} तक के सभी अवयव ों को वर्गीकृत कर दिया है, और {{mvar|A<sub>i</sub>}} को एक संभावित नए चक्र नेता के रूप में मान रहे हैं। इसके लक्ष्य बकेट {{mvar|b}} की गणना करना आसान है। लूप इनवेरिएंट द्वारा, इसे वर्गीकृत किया जाता है यदि {{math|''L<sub>b</sub>'' &lt; ''i'' ≤ ''K<sub>b</sub>''}}, और यदि {{mvar|i}} उस सीमा से बाहर है तो अवर्गीकृत किया जाता है। पहली असमानता का परीक्षण करना आसान है, किंतु दूसरे के लिए मान {{mvar|K<sub>b</sub>}} की आवश्यकता होती है।
-इससे पता चलता है कि [[प्रेरण परिकल्पना]] सभी तत्वों तक पहुँचती है {{math|''i''&minus;1}} वर्गीकृत किये जाने का तात्पर्य यह है कि {{math|''i'' ≤ ''K<sub>b</sub>''}}, इसलिए दूसरी असमानता का परीक्षण करना आवश्यक नहीं है।
+यह पता चलता है कि प्रेरण परिकल्पना कि {{math|''i''&minus;1}} तक के सभी अवयव ों को वर्गीकृत किया गया है, इसका तात्पर्य है कि {{math|''i'' ≤ ''K<sub>b</sub>''}}, इसलिए दूसरी असमानता का परीक्षण करना आवश्यक नहीं है।
-बाल्टी पर विचार करें {{mvar|c}} कौन सी स्थिति {{mvar|i}} अंदर गिरा। वह है, {{math|''K''<sub>''c''&minus;1</sub> &lt; ''i'' ≤ ''K<sub>c</sub>''}}. प्रेरण परिकल्पना के अनुसार, नीचे दिए गए सभी तत्व {{mvar|i}}, जिसमें तक की सभी बकेट शामिल हैं {{math|''K''<sub>''c''&minus;1</sub> &lt; ''i''}}, पूर्णतः वर्गीकृत हैं। अर्थात। उन बकेट में शामिल कोई भी तत्व शेष सरणी में नहीं रहता है। इसलिए ऐसा संभव नहीं है {{math|''b'' &lt; ''c''}}.
+बकेट {{mvar|c}} पर विचार करें जो {{mvar|i}} स्थिति में आती है। अर्थात्, {{math|''K''<sub>''c''&minus;1</sub> &lt; ''i'' ≤ ''K<sub>c</sub>''}}. प्रेरण परिकल्पना के अनुसार, नीचे दिए गए सभी अवयव  {{mvar|i}}, जिसमें {{math|''K''<sub>''c''&minus;1</sub> &lt; ''i''}}तक की सभी बकेट सम्मिलित हैं, पूरी तरह से वर्गीकृत हैं। अर्थात। उन बकेट में सम्मिलित कोई भी अवयव  शेष सरणी में नहीं रहता है। इसलिए, यह संभव नहीं है कि {{math|''b'' &lt; ''c''}}.
-एकमात्र मामला शेष है {{math|''b'' ≥ ''c''}}, जो ये दर्शाता हे {{math|''K<sub>b</sub>'' ≥ ''K<sub>c</sub>'' ≥ ''i''}}, क्यू.ई.डी.
+एकमात्र शेष स्थिति b ≥ c है, जिसका अर्थ है {{math|''K<sub>b</sub>'' ≥ ''K<sub>c</sub>'' ≥ ''i''}}, Q.E.D.
-इसे शामिल करते हुए, फ्लैशसॉर्ट वितरण एल्गोरिदम शुरू होता है {{mvar|L}} जैसा कि ऊपर वर्णित है और {{math|1=''i'' = 1}}. फिर आगे बढ़ें:<ref name="neubert_journal" /><ref name="neubert_code">{{cite web |url=http://www.neubert.net/FSOIntro.html |title=फ्लैशसॉर्ट एल्गोरिथम|access-date=2007-11-06 |last=Neubert |first=Karl-Dietrich |year=1998}}</ref>
+इसे सम्मिलित करते हुए, फ्लैशसॉर्ट वितरण एल्गोरिदम ऊपर बताए अनुसार {{mvar|L}} से प्रारंभ होता है और {{math|1=''i'' = 1}}. फिर आगे बढ़ें:<ref name="neubert_journal" /><ref name="neubert_code">{{cite web |url=http://www.neubert.net/FSOIntro.html |title=फ्लैशसॉर्ट एल्गोरिथम|access-date=2007-11-06 |last=Neubert |first=Karl-Dietrich |year=1998}}</ref>
-* अगर {{math|''i'' &gt; ''n''}}, वितरण पूर्ण हो गया है।
+* यदि{{math|''i'' &gt; ''n''}} तो वितरण पूरा हो गया है।
-* दिया गया {{mvar|A<sub>i</sub>}}, बाल्टी की गणना करें {{mvar|b}} जिससे यह संबंधित है।
+*{{mvar|A<sub>i</sub>}} को देखते हुए, उस बकेट  b की गणना करें जिससे वह संबंधित है।
-* अगर {{math|''i'' ≤ ''L<sub>b</sub>''}}, तब {{mvar|A<sub>i</sub>}} अवर्गीकृत है. इसे एक अस्थायी चर की प्रतिलिपि बनाएँ {{mvar|t}} और:
+*यदि {{math|''i'' ≤ ''L<sub>b</sub>''}}, तो {{mvar|A<sub>i</sub>}} अवर्गीकृत है। इसे एक अस्थायी चर t प्रतिलिपि करें और:
-** होने देना {{math|1=''j'' = ''L<sub>b</sub>''}} वह स्थान हो जहां {{mvar|t}} संग्रहित किया जाएगा.
+**मान लीजिए {{math|1=''j'' = ''L<sub>b</sub>''}} वह स्थान है जहाँ t संग्रहीत किया जाएगा।
-** अदला-बदली {{mvar|t}} साथ {{mvar|A<sub>j</sub>}}, अर्थात। इकट्ठा करना {{mvar|t}} में {{mvar|A<sub>j</sub>}} पिछला मान लाते समय {{mvar|A<sub>j</sub>}} जिससे विस्थापित हो गया।
+**t को {{mvar|A<sub>j</sub>}} के साथ बदलें, अर्थात पिछले मान {{mvar|A<sub>j</sub>}}को प्राप्त करते समय t को {{mvar|A<sub>j</sub>}}में संग्रहीत करें जिससे {{mvar|A<sub>j</sub>}}विस्थापित हो जाए।
-** कमी {{mvar|L<sub>b</sub>}} इस तथ्य को प्रतिबिंबित करने के लिए {{mvar|A<sub>j</sub>}} अब सही ढंग से वर्गीकृत किया गया है।
+**इस तथ्य को प्रतिबिंबित करने के लिए {{mvar|L<sub>b</sub>}} घटाएं कि {{mvar|A<sub>j</sub>}}को अब सही रूप से वर्गीकृत किया गया है।
-** अगर {{math|''j'' ≠ ''i''}}, बाल्टी की गणना करें {{mvar|b}} किसको {{mvar|t}} संबंधित है और इस (आंतरिक) लूप को नए के साथ पुनः आरंभ करें {{mvar|t}}.
+**यदि {{math|''j'' ≠ ''i''}}, तो उस बकेट {{mvar|b}} की गणना करें जिससे t संबंधित है और इस (आंतरिक) लूप को नए {{mvar|t}} के साथ पुनरारंभ करें।
-* {{mvar|A<sub>i</sub>}} अब सही ढंग से वर्गीकृत किया गया है। वेतन वृद्धि {{mvar|i}} और (बाहरी) लूप को पुनरारंभ करें।
+* {{mvar|A<sub>i</sub>}} अब सही रूप  से वर्गीकृत किया गया है। वेतन वृद्धि {{mvar|i}} और (बाहरी) लूप को पुनरारंभ करें।
-मेमोरी को सहेजते समय, फ्लैशसॉर्ट का नुकसान यह है कि यह पहले से ही वर्गीकृत कई तत्वों के लिए बकेट की पुन: गणना करता है। यह पहले से ही प्रति तत्व दो बार किया जाता है (एक बार बाल्टी-गिनती चरण के दौरान और दूसरी बार प्रत्येक तत्व को स्थानांतरित करते समय), लेकिन पहले अवर्गीकृत तत्व की खोज के लिए अधिकांश तत्वों के लिए तीसरी गणना की आवश्यकता होती है। यह महंगा हो सकता है यदि बाल्टियों को सरल रैखिक प्रक्षेप की तुलना में अधिक जटिल सूत्र का उपयोग करके निर्दिष्ट किया जाता है। एक वैरिएंट गणनाओं की संख्या को लगभग कम कर देता है {{math|3''n''}}अधिक से अधिक {{math|2''n''&nbsp;+&nbsp;''m''&nbsp;&minus;&nbsp;1}} अधूरी बाल्टी में अंतिम अवर्गीकृत तत्व को साइकिल लीडर के रूप में लेकर:
+मेमोरी को सहेजते समय, फ्लैशसॉर्ट का हानि यह है कि यह पहले से ही वर्गीकृत कई अवयव के लिए बकेट की पुन: गणना करता है। यह पहले से ही प्रति अवयव  दो बार किया जाता है (एक बार बकेट -गिनती चरण के समय  और दूसरी बार प्रत्येक अवयव  को स्थानांतरित करते समय), किंतु पहले अवर्गीकृत अवयव  की खोज के लिए अधिकांश अवयव के लिए तीसरी गणना की आवश्यकता होती है। यह मूल्यवान हो सकता है यदि बकेट को सरल रैखिक प्रक्षेप की तुलना में अधिक जटिल सूत्र का उपयोग करके निर्दिष्ट किया जाता है। एक प्रकार चक्र लीडर के रूप में एक अधूरी बकेट में अंतिम अवर्गीकृत तत्व को लेकर गणनाओं की संख्या को लगभग {{math|3''n''}} से घटाकर अधिकतम {{math|2''n''&nbsp;+&nbsp;''m''&nbsp;&minus;&nbsp;1}} कर देता है:
-* एक वैरिएबल बनाए रखें {{mvar|c}} पहली अपूर्ण-वर्गीकृत बाल्टी की पहचान करना। होने देना {{math|1=''c'' = 1}} शुरू करने के लिए, और कब {{mvar|''c'' &gt; ''m''}}, वितरण पूर्ण हो गया है।
+*पहले अपूर्ण-वर्गीकृत बकेट की पहचान करने वाला एक वेरिएबल c बनाए रखें। आरंभ करने के लिए मान लीजिए c = 1 है, और जब c > m वितरण पूरा हो जाता है।
-* होने देना {{math|1=''i'' = ''L<sub>c</sub>''}}. अगर {{math|1=''i'' = ''L''<sub>''c''&minus;1</sub>}}, वृद्धि {{mvar|c}} और इस लूप को पुनरारंभ करें। ({{math|1=''L''<sub>0</sub> = 0}}.)
+*चलो {{math|1=''i'' = ''L<sub>c</sub>''}}. यदि {{math|1=''i'' = ''L''<sub>''c''&minus;1</sub>}} है, तो c बढ़ाएँ और इस लूप को पुनरारंभ करें। (L0 = 0.)
-* बाल्टी की गणना करें {{mvar|b}} किसको {{mvar|A<sub>i</sub>}} का है.
+*उस बकेट b की गणना करें जिससे {{mvar|A<sub>i</sub>}} संबंधित है।
-* अगर {{math|''b'' &lt; ''c''}}, तब {{math|1=''L<sub>c</sub>'' = ''K''<sub>''c''&minus;1</sub>}} और हमारा बाल्टी से काम पूरा हो गया {{mvar|c}}. वेतन वृद्धि {{mvar|c}} और इस लूप को पुनरारंभ करें।
+*यदि b < c, तो {{math|1=''L<sub>c</sub>'' = ''K''<sub>''c''&minus;1</sub>}} और हमने बकेट c का काम पूरा कर लिया है। {{mvar|c}} बढ़ाएँ और इस लूप को पुनरारंभ करें।
-* अगर {{math|1=''b'' = ''c''}}, वर्गीकरण तुच्छ है. घटती {{mvar|L<sub>c</sub>}} और इस लूप को पुनरारंभ करें।
+*यदि b = c है, तो वर्गीकरण तुच्छ है। {{mvar|L<sub>c</sub>}} घटाएं और इस लूप को पुनरारंभ करें।
-* अगर  {{math|''b'' &gt; ''c''}}, तब {{mvar|A<sub>i</sub>}} अवर्गीकृत है. पिछले मामले की तरह ही वर्गीकरण लूप निष्पादित करें, फिर इस लूप को पुनरारंभ करें।
+*यदि b > c, तो {{mvar|A<sub>i</sub>}} अवर्गीकृत है। पिछले स्थिति की तरह ही वर्गीकरण लूप निष्पादित करें और फिर इस लूप को पुनरारंभ करें।
-अधिकांश तत्वों की बकेट की गणना केवल दो बार की जाती है, प्रत्येक बकेट में अंतिम तत्व को छोड़कर, जिसका उपयोग निम्नलिखित बकेट के पूरा होने का पता लगाने के लिए किया जाता है। अवर्गीकृत तत्वों की गिनती बनाए रखने और शून्य तक पहुंचने पर रोककर थोड़ी और कमी हासिल की जा सकती है।
+अधिकांश अवयव की बकेट की गणना केवल दो बार की जाती है, प्रत्येक बकेट में अंतिम अवयव  को छोड़कर, जिसका उपयोग निम्नलिखित बकेट के पूरा होने का पता लगाने के लिए किया जाता है। अवर्गीकृत अवयव  की गिनती बनाए रखने और शून्य तक पहुंचने पर रोककर थोड़ी और कमी प्राप्त की जा सकती है।
 == प्रदर्शन ==
-एकमात्र अतिरिक्त मेमोरी आवश्यकताएँ सहायक वेक्टर हैं {{mvar|L}} बकेट सीमा और उपयोग किए गए अन्य चर की निरंतर संख्या को संग्रहीत करने के लिए। इसके अलावा, प्रत्येक तत्व को केवल एक बार स्थानांतरित किया जाता है (एक अस्थायी बफर के माध्यम से, इसलिए दो चाल संचालन)। हालाँकि, यह मेमोरी दक्षता इस नुकसान के साथ आती है कि सरणी को यादृच्छिक रूप से एक्सेस किया जाता है, इसलिए संपूर्ण सरणी से छोटे [[डेटा कैश]] का लाभ नहीं उठाया जा सकता है।
+एकमात्र अतिरिक्त मेमोरी आवश्यकताएं बकेट सीमा और उपयोग किए गए अन्य चर की निरंतर संख्या को संग्रहीत करने के लिए सहायक वेक्टर {{mvar|L}} हैं। इसके अतिरिक्त , प्रत्येक अवयव  को केवल एक बार स्थानांतरित किया जाता है (एक अस्थायी बफर के माध्यम से, इसलिए दो चाल संचालन)। चूँकि, यह मेमोरी दक्षता इस हानि के साथ आती है कि सरणी को यादृच्छिक रूप से एक्सेस किया जाता है, इसलिए संपूर्ण सरणी से छोटे [[डेटा कैश]] का लाभ नहीं उठाया जा सकता है।
-सभी बकेट प्रकारों की तरह, प्रदर्शन गंभीर रूप से बकेट के संतुलन पर निर्भर करता है। संतुलित डेटा सेट के आदर्श मामले में, प्रत्येक बाल्टी लगभग समान आकार की होगी। यदि संख्या {{mvar|m}} बकेट का इनपुट आकार रैखिक है {{mvar|n}}, प्रत्येक बाल्टी का एक स्थिर आकार होता है, इसलिए एक बाल्टी को एक के साथ क्रमबद्ध करें {{math|''O''(''n''<sup>2</sup>)}} इंसर्शन सॉर्ट जैसे एल्गोरिदम में जटिलता होती है {{math|1=''O''(1<sup>2</sup>) = ''O''(1)}}. अंतिम प्रविष्टि सॉर्ट का चलने का समय इसलिए है {{math|1=''m'' ⋅ O(1) = ''O''(''m'') = ''O''(''n'')}}.
+सभी बकेट प्रकारों की तरह, प्रदर्शन गंभीर रूप से बकेट के संतुलन पर निर्भर करता है। संतुलित डेटा सेट के आदर्श स्थिति में, प्रत्येक बकेट लगभग समान आकार की होगी। यदि इनपुट आकार n में बकेट की संख्या {{mvar|m}} रैखिक है, तो प्रत्येक बकेट का एक स्थिर आकार होता है, इसलिए एक एकल बकेट को {{math|''O''(''n''<sup>2</sup>)}} एल्गोरिदम जैसे प्रविष्टि सॉर्ट के साथ सॉर्ट करने में जटिलता {{math|1=''O''(1<sup>2</sup>) = ''O''(1)}} होती है। इसलिए अंतिम प्रविष्टि प्रकार का चलने का समय {{math|1=''m'' ⋅ O(1) = ''O''(''m'') = ''O''(''n'')}} है।
-के लिए एक मान चुनना {{mvar|m}}, बाल्टियों की संख्या, तत्वों को वर्गीकृत करने में लगने वाले समय को कम कर देती है (उच्च)। {{mvar|m}}) और अंतिम प्रविष्टि सॉर्ट चरण में बिताया गया समय (कम)। {{mvar|m}}). उदाहरण के लिए, यदि {{mvar|m}} को आनुपातिक रूप से चुना गया है {{math|{{sqrt|''n''}}}}, तो अंतिम प्रविष्टि प्रकार का चलने का समय इसलिए है {{math|1=''m'' ⋅ O({{math|{{sqrt|''n''}}<sup>2</sup>}}) = ''O''(''n''<sup>3/2</sup>)}}.
+{{mvar|m}} के लिए एक मान चुनना, बकेट की संख्या, तत्वों को वर्गीकृत करने में लगने वाला समय (उच्च {{mvar|m}}) और अंतिम प्रविष्टि सॉर्ट चरण (कम {{mvar|m}}) में लगने वाला समय कम हो जाता है। उदाहरण के लिए, यदि m को {{math|{{sqrt|''n''}}}} के आनुपातिक रूप से चुना गया है, तो अंतिम प्रविष्टि प्रकार का चलने का समय {{math|1=''m'' ⋅ O({{math|{{sqrt|''n''}}<sup>2</sup>}}) = ''O''(''n''<sup>3/2</sup>)}} है।
-सबसे खराब स्थिति में जहां लगभग सभी तत्व कुछ बकेट में होते हैं, एल्गोरिदम की जटिलता अंतिम बकेट-सॉर्टिंग विधि के प्रदर्शन से सीमित होती है, इसलिए इसमें गिरावट आती है {{math|''O''(''n''<sup>2</sup>)}}. एल्गोरिदम की विविधताएं एक निश्चित आकार सीमा से अधिक की बाल्टियों पर बेहतर प्रदर्शन करने वाले प्रकारों जैसे [[जल्दी से सुलझाएं]] या रिकर्सिव फ्लैशसॉर्ट का उपयोग करके सबसे खराब स्थिति के प्रदर्शन में सुधार करती हैं।<ref name="neubert_code" /><ref>{{cite journal
+सबसे व्यर्थ स्थिति में जहां लगभग सभी तत्व कुछ बकेट में होते हैं, एल्गोरिदम की जटिलता अंतिम बकेट-सॉर्टिंग विधि के प्रदर्शन से सीमित होती है, इसलिए यह {{math|''O''(''n''<sup>2</sup>)}} तक घट जाती है। एल्गोरिदम की विविधताएं एक निश्चित आकार सीमा से अधिक की बकेट पर उत्तम प्रदर्शन करने वाले प्रकारों जैसे क्विकसॉर्ट या रिकर्सिव फ्लैशसॉर्ट का उपयोग करके सबसे व्यर्थ स्थिति के प्रदर्शन में सुधार करती हैं।।<ref name="neubert_code" /><ref>{{cite journal
   |first1=Li |last1=Xiao
   |first2=Xiaodong |last2=Zhang
@@ Line 86: / Line 88: @@
   |url-status=dead
 }}</ref>
-के लिए {{math|1=''m'' = 0.1 ''n''}} समान रूप से वितरित यादृच्छिक डेटा के साथ, फ्लैशसॉर्ट सभी के लिए [[ढेर बनाएं और छांटें]] से तेज है {{mvar|n}} और क्विकसॉर्ट से तेज़ {{math|''n'' > 80}}. यह क्विकसॉर्ट की तुलना में लगभग दोगुना तेज़ हो जाता है {{math|1=''n'' = 10000}}.<ref name="neubert_journal" />  ध्यान दें कि ये माप 1990 के दशक के अंत में लिए गए थे, जब मेमोरी पदानुक्रम कैशिंग पर बहुत कम निर्भर था।<!--As can be seen by benchmarks maxing out at n=10000, which is "fits into L1 cache" these days.-->
-फ्लैशसॉर्ट अपनी वर्गीकरण प्रक्रिया में जो यथास्थान क्रमपरिवर्तन करता है, उसके कारण फ्लैशसॉर्ट स्थिर सॉर्ट#स्थिरता नहीं है। यदि स्थिरता की आवश्यकता है, तो दूसरी सरणी का उपयोग करना संभव है ताकि तत्वों को क्रमिक रूप से वर्गीकृत किया जा सके। हालाँकि, इस मामले में, एल्गोरिदम की आवश्यकता होगी {{math|''O''(''n'')}} अतिरिक्त मेमोरी.
+समान रूप से वितरित यादृच्छिक डेटा के साथ {{math|1=''m'' = 0.1 ''n''}} के लिए, फ्लैशसॉर्ट सभी {{mvar|n}} के लिए हीप्सॉर्ट से तेज है और {{math|''n'' > 80}} के लिए क्विकॉर्ट से तेज है। यह {{math|1=''n'' = 10000}} पर क्विकॉर्ट से लगभग दोगुना तेज हो जाता है। ध्यान दें कि ये माप 1990 के दशक के अंत में लिए गए थे, जब मेमोरी पदानुक्रम कैशिंग पर बहुत कम निर्भर थे।
+फ्लैशसॉर्ट अपनी वर्गीकरण प्रक्रिया में जो यथास्थान क्रमपरिवर्तन करता है, उसके कारण फ्लैशसॉर्ट स्थिर नहीं है। यदि स्थिरता की आवश्यकता है, तो दूसरी सरणी का उपयोग करना संभव है जिससे तत्वों को क्रमिक रूप से वर्गीकृत किया जा सके। चूँकि, इस स्थिति में, एल्गोरिदम को {{math|''O''(''n'')}} अतिरिक्त मेमोरी की आवश्यकता होगी।
 == यह भी देखें ==
-* सॉर्टिंग के बजाय खोज एल्गोरिदम के लिए वस्तुओं के वितरण का उपयोग करके [[अंतर्वेशन खोज]]
+*प्रक्षेप खोज, सॉर्टिंग के अतिरिक्त खोज के लिए वस्तुओं के वितरण का उपयोग करना
 == संदर्भ ==

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

Revision as of 11:20, 14 July 2023

Contents

संकल्पना

मेमोरी कुशल कार्यान्वयन

प्रदर्शन

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

फ्लैशसॉर्ट: Difference between revisions

Revision as of 11:20, 14 July 2023

संकल्पना

मेमोरी कुशल कार्यान्वयन

प्रदर्शन

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories