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

फ्लैशसॉर्ट एक सॉर्टिंग एल्गोरिदम#डिस्ट्रीब्यूशन सॉर्ट्स एल्गोरिदम है जो ओ नोटेशन|रैखिक कम्प्यूटेशनल जटिलता दिखाता है {{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}} निम्नलिखित नुसार:

# इनपुट पर पहले पास या प्राथमिक ज्ञान का उपयोग करके, न्यूनतम और अधिकतम सॉर्ट कुंजी ढूंढें।

# रेंज को रैखिक रूप से विभाजित करें {{math|[''A''_min, ''A''_max]}} में {{mvar|m}} बाल्टियाँ।

# तत्वों की संख्या गिनते हुए, इनपुट पर एक पास बनाएं {{mvar|A_i}} जो प्रत्येक बाल्टी में गिरती है। (न्यूबर्ट बकेट क्लासेस और तत्वों के असाइनमेंट को उनके बकेट वर्गीकरण कहते हैं।)

# प्रत्येक बकेट में तत्वों की संख्या को [[उपसर्ग योग]] में बदलें, जहां {{mvar|L_b}}तत्वों की संख्या है {{mvar|A_i}} बाल्टी में {{mvar|b}} या कम। ({{math|1=''L''₀ = 0}} और {{math|1=''L_m'' = ''n''}}.)

# प्रत्येक बकेट के सभी तत्वों में इनपुट को पुनर्व्यवस्थित करें {{mvar|b}} पदों पर संग्रहीत हैं {{mvar|A_i}} कहाँ {{math|''L''_{''b''&minus;1} &lt; ''i'' ≤ ''L_b''}}.

चरण 1-3 और 6 किसी भी बकेट सॉर्ट के लिए सामान्य हैं, और बकेट सॉर्ट के लिए सामान्य तकनीकों का उपयोग करके इसमें सुधार किया जा सकता है। विशेष रूप से, लक्ष्य यह है कि बाल्टियाँ लगभग समान आकार की हों ({{math|''n''/''m''}}तत्व प्रत्येक),<ref name="neubert_journal" /> आदर्श विभाजन के साथ {{mvar|m}} मात्राएँ। जबकि मूल एल्गोरिथ्म एक रैखिक प्रक्षेप प्रकार है, यदि इनपुट संभाव्यता वितरण को गैर-समान माना जाता है, तो एक गैर-रेखीय विभाजन इस आदर्श को अधिक निकटता से अनुमानित करेगा। इसी तरह, अंतिम सॉर्ट पुनरावर्ती फ़्लैश सॉर्ट सहित कई तकनीकों में से किसी एक का उपयोग कर सकता है।

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

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

प्रति बाल्टी दो (शब्द-आकार) चर का उपयोग करके विवरण को समझना आसान है। चतुर हिस्सा उन चरों में से एक को खत्म करना है, जिससे दोगुनी बाल्टियों का उपयोग किया जा सकता है और इसलिए अंतिम पर आधा समय खर्च किया जा सकता है। {{math|''O''(''n''²)}} छंटाई.

प्रति बाल्टी दो चर के साथ इसे समझने के लिए, मान लें कि दो सारणियाँ हैं {{mvar|m}}अतिरिक्त शब्द: {{mvar|K_b}} बाल्टी की (निश्चित) ऊपरी सीमा है {{mvar|b}} (और {{math|1=''K''₀ = 0}}), जबकि {{mvar|L_b}} बकेट में एक (चलने योग्य) सूचकांक है {{mvar|b}}, इसलिए {{math|''K''_{''b''&minus;1} ≤ ''L_b'' ≤ ''K_b''}}.

हम लूप को अपरिवर्तनीय बनाए रखते हैं जिससे प्रत्येक बाल्टी विभाजित होती है {{mvar|L_b}} एक अवर्गीकृत उपसर्ग में ({{mvar|A_i}} के लिए {{math|''K''_{''b''&minus;1} &lt; ''i'' ≤ ''L_b''}} को अभी तक उनके लक्ष्य बकेट में ले जाया जाना बाकी है) और एक वर्गीकृत प्रत्यय ({{mvar|A_i}} के लिए {{math|''L_b'' &lt; ''i'' ≤ ''K_b''}} सभी सही बकेट में हैं और इन्हें दोबारा स्थानांतरित नहीं किया जाएगा)। शुरू में {{math|1=''L_b'' = ''K_b''}} और सभी तत्व अवर्गीकृत हैं। जैसे-जैसे छँटाई आगे बढ़ती है, {{mvar|L_b}} तक घटे हैं {{math|1=''L_b'' = ''K''_{''b''&minus;1}}} सभी के लिए {{mvar|b}} और सभी तत्वों को सही बकेट में वर्गीकृत किया गया है।

प्रत्येक दौर की शुरुआत पहली अपूर्ण रूप से वर्गीकृत बाल्टी को खोजने से होती है {{mvar|c}} (जो है {{math|''K''_{''c''&minus;1} &lt; ''L_c''}}) और उस बकेट में पहला अवर्गीकृत तत्व लेना {{mvar|A_i}} कहाँ {{math|1=''i'' = ''K''_{''c''&minus;1} + 1}}. (न्यूबर्ट इसे साइकिल लीडर कहते हैं।) प्रतिलिपि {{mvar|A_i}} एक अस्थायी चर के लिए {{mvar|t}} और दोहराओ:

* बाल्टी की गणना करें {{mvar|b}} किसको {{mvar|t}} का है.

* होने देना {{math|1=''j'' = ''L_b''}} वह स्थान हो जहां {{mvar|t}} संग्रहित किया जाएगा.

* अदला-बदली {{mvar|t}} साथ {{mvar|A_j}}, अर्थात। इकट्ठा करना {{mvar|t}} में {{mvar|A_j}} पिछला मान लाते समय {{mvar|A_j}} जिससे विस्थापित हो गया।

*घटना {{mvar|L_b}} इस तथ्य को प्रतिबिंबित करने के लिए {{mvar|A_j}} अब सही ढंग से वर्गीकृत किया गया है।

* अगर {{math|''j'' ≠ ''i''}}, इस लूप को नए के साथ पुनरारंभ करें {{mvar|t}}.

* अगर {{math|1=''j'' = ''i''}}, यह दौर समाप्त हो गया है और एक नया पहला अवर्गीकृत तत्व ढूंढें {{mvar|A_i}}.

* जब कोई अवर्गीकृत तत्व नहीं रह जाते हैं, तो बाल्टियों में वितरण पूरा हो जाता है।

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

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

मान लीजिए कि हमने सभी तत्वों को वर्गीकृत कर दिया है {{math|''i''&minus;1}}, और विचार कर रहे हैं {{mvar|A_i}} एक संभावित नए साइकिल नेता के रूप में। इसके लक्ष्य बकेट की गणना करना आसान है {{mvar|b}}. लूप इनवेरिएंट द्वारा, इसे वर्गीकृत किया गया है {{math|''L_b'' &lt; ''i'' ≤ ''K_b''}}, और अवर्गीकृत यदि {{mvar|i}} उस सीमा से बाहर है. पहली [[असमानता (गणित)]] का परीक्षण करना आसान है, लेकिन दूसरे के लिए मूल्य की आवश्यकता होती है {{mvar|K_b}}.

इससे पता चलता है कि [[प्रेरण परिकल्पना]] सभी तत्वों तक पहुँचती है {{math|''i''&minus;1}} वर्गीकृत किये जाने का तात्पर्य यह है कि {{math|''i'' ≤ ''K_b''}}, इसलिए दूसरी असमानता का परीक्षण करना आवश्यक नहीं है।

बाल्टी पर विचार करें {{mvar|c}} कौन सी स्थिति {{mvar|i}} अंदर गिरा। वह है, {{math|''K''_{''c''&minus;1} &lt; ''i'' ≤ ''K_c''}}. प्रेरण परिकल्पना के अनुसार, नीचे दिए गए सभी तत्व {{mvar|i}}, जिसमें तक की सभी बकेट शामिल हैं {{math|''K''_{''c''&minus;1} &lt; ''i''}}, पूर्णतः वर्गीकृत हैं। अर्थात। उन बकेट में शामिल कोई भी तत्व शेष सरणी में नहीं रहता है। इसलिए ऐसा संभव नहीं है {{math|''b'' &lt; ''c''}}.

एकमात्र मामला शेष है {{math|''b'' ≥ ''c''}}, जो ये दर्शाता हे {{math|''K_b'' ≥ ''K_c'' ≥ ''i''}}, क्यू.ई.डी.

इसे शामिल करते हुए, फ्लैशसॉर्ट वितरण एल्गोरिदम शुरू होता है {{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''}}, वितरण पूर्ण हो गया है।

* दिया गया {{mvar|A_i}}, बाल्टी की गणना करें {{mvar|b}} जिससे यह संबंधित है।

* अगर {{math|''i'' ≤ ''L_b''}}, तब {{mvar|A_i}} अवर्गीकृत है. इसे एक अस्थायी चर की प्रतिलिपि बनाएँ {{mvar|t}} और:

** होने देना {{math|1=''j'' = ''L_b''}} वह स्थान हो जहां {{mvar|t}} संग्रहित किया जाएगा.

** अदला-बदली {{mvar|t}} साथ {{mvar|A_j}}, अर्थात। इकट्ठा करना {{mvar|t}} में {{mvar|A_j}} पिछला मान लाते समय {{mvar|A_j}} जिससे विस्थापित हो गया।

** कमी {{mvar|L_b}} इस तथ्य को प्रतिबिंबित करने के लिए {{mvar|A_j}} अब सही ढंग से वर्गीकृत किया गया है।

** अगर {{math|''j'' ≠ ''i''}}, बाल्टी की गणना करें {{mvar|b}} किसको {{mvar|t}} संबंधित है और इस (आंतरिक) लूप को नए के साथ पुनः आरंभ करें {{mvar|t}}.

* {{mvar|A_i}} अब सही ढंग से वर्गीकृत किया गया है। वेतन वृद्धि {{mvar|i}} और (बाहरी) लूप को पुनरारंभ करें।

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

* एक वैरिएबल बनाए रखें {{mvar|c}} पहली अपूर्ण-वर्गीकृत बाल्टी की पहचान करना। होने देना {{math|1=''c'' = 1}} शुरू करने के लिए, और कब {{mvar|''c'' &gt; ''m''}}, वितरण पूर्ण हो गया है।

* होने देना {{math|1=''i'' = ''L_c''}}. अगर {{math|1=''i'' = ''L''_{''c''&minus;1}}}, वृद्धि {{mvar|c}} और इस लूप को पुनरारंभ करें। ({{math|1=''L''₀ = 0}}.)

* बाल्टी की गणना करें {{mvar|b}} किसको {{mvar|A_i}} का है.

* अगर {{math|''b'' &lt; ''c''}}, तब {{math|1=''L_c'' = ''K''_{''c''&minus;1}}} और हमारा बाल्टी से काम पूरा हो गया {{mvar|c}}. वेतन वृद्धि {{mvar|c}} और इस लूप को पुनरारंभ करें।

* अगर {{math|1=''b'' = ''c''}}, वर्गीकरण तुच्छ है. घटती {{mvar|L_c}} और इस लूप को पुनरारंभ करें।

* अगर  {{math|''b'' &gt; ''c''}}, तब {{mvar|A_i}} अवर्गीकृत है. पिछले मामले की तरह ही वर्गीकरण लूप निष्पादित करें, फिर इस लूप को पुनरारंभ करें।

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

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

सभी बकेट प्रकारों की तरह, प्रदर्शन गंभीर रूप से बकेट के संतुलन पर निर्भर करता है। संतुलित डेटा सेट के आदर्श मामले में, प्रत्येक बाल्टी लगभग समान आकार की होगी। यदि संख्या {{mvar|m}} बकेट का इनपुट आकार रैखिक है {{mvar|n}}, प्रत्येक बाल्टी का एक स्थिर आकार होता है, इसलिए एक बाल्टी को एक के साथ क्रमबद्ध करें {{math|''O''(''n''²)}} इंसर्शन सॉर्ट जैसे एल्गोरिदम में जटिलता होती है {{math|1=''O''(1²) = ''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''}}²}}) = ''O''(''n''^3/2)}}.

सबसे खराब स्थिति में जहां लगभग सभी तत्व कुछ बकेट में होते हैं, एल्गोरिदम की जटिलता अंतिम बकेट-सॉर्टिंग विधि के प्रदर्शन से सीमित होती है, इसलिए इसमें गिरावट आती है {{math|''O''(''n''²)}}. एल्गोरिदम की विविधताएं एक निश्चित आकार सीमा से अधिक की बाल्टियों पर बेहतर प्रदर्शन करने वाले प्रकारों जैसे [[जल्दी से सुलझाएं]] या रिकर्सिव फ्लैशसॉर्ट का उपयोग करके सबसे खराब स�