फ्लैशसॉर्ट: Difference between revisions
No edit summary |
No edit summary |
||
| Line 5: | Line 5: | ||
== संकल्पना == | == संकल्पना == | ||
फ्लैशसॉर्ट हिस्टोग्राम सॉर्ट का एक कुशल इन-प्लेस कार्यान्वयन है, जो स्वयं एक प्रकार का बकेट सॉर्ट है। यह प्रत्येक n इनपुट अवयव | फ्लैशसॉर्ट हिस्टोग्राम सॉर्ट का एक कुशल इन-प्लेस कार्यान्वयन है, जो स्वयं एक प्रकार का बकेट सॉर्ट है। यह प्रत्येक n इनपुट अवयव को m बकेट में से एक को निर्दिष्ट करता है, बकेट को सही क्रम में रखने के लिए इनपुट को कुशलतापूर्वक पुनर्व्यवस्थित करता है, फिर प्रत्येक बकेट को सॉर्ट करता है। मूल एल्गोरिदम एक इनपुट सरणी {{mvar|A}} को निम्नानुसार सॉर्ट करता है: | ||
* इनपुट पर पहले पास या प्राथमिक ज्ञान का उपयोग करके न्यूनतम और अधिकतम सॉर्ट कुंजी खोजे । | |||
* रेंज [''A''<sub>min</sub>, ''A''<sub>max</sub>] को रैखिक रूप से m बकेट में विभाजित करें। | |||
* प्रत्येक बकेट में गिरने वाले A<sub>i</sub> अवयव की संख्या गिनते हुए, इनपुट पर एक पास बनाते है। (न्यूबर्ट बकेट को "वर्ग" और उनकी बकेट में अवयव के असाइनमेंट को "वर्गीकरण" कहते हैं।) | |||
* प्रत्येक बकेट में अवयव की संख्या को उपसर्ग योग में बदलें, जहां L<sub>b</sub> बकेट b या उससे कम में अवयव A<sub>i</sub> की संख्या है। (L0 = 0 और Lm = n.) | |||
* प्रत्येक बकेट b के सभी अवयव के इनपुट को पुनर्व्यवस्थित करें, स्थिति A<sub>i</sub> में संग्रहीत किया जाता है जहां ''L<sub>b</sub>''<sub>−1</sub> < ''i'' ≤ ''L<sub>b</sub>''। | |||
* [[सम्मिलन सॉर्ट]] का उपयोग करके प्रत्येक बकेट को सॉर्ट करें। | |||
चरण 1-3 और 6 किसी भी बकेट सॉर्ट के लिए सामान्य हैं, और बकेट सॉर्ट के लिए सामान्य तकनीकों का उपयोग करके इसमें सुधार किया जा सकता है। विशेष रूप से, लक्ष्य यह है कि बकेट लगभग समान आकार (प्रत्येक{{math|''n''/''m''}} अवयव ) की हों<ref name="neubert_journal" /> जिसका आदर्श रूप m मात्राओं में विभाजन है। जबकि मूल एल्गोरिथ्म एक रैखिक प्रक्षेप प्रकार है, यदि इनपुट वितरण को गैर-समान माना जाता है, तो एक गैर-रेखीय विभाजन इस आदर्श को अधिक निकटता से अनुमानित करेगा। इसी तरह अंतिम सॉर्ट पुनरावर्ती फ़्लैश सॉर्ट सहित कई तकनीकों में से किसी एक का उपयोग कर सकता है। | चरण 1-3 और 6 किसी भी बकेट सॉर्ट के लिए सामान्य हैं, और बकेट सॉर्ट के लिए सामान्य तकनीकों का उपयोग करके इसमें सुधार किया जा सकता है। विशेष रूप से, लक्ष्य यह है कि बकेट लगभग समान आकार (प्रत्येक{{math|''n''/''m''}} अवयव ) की हों<ref name="neubert_journal" /> जिसका आदर्श रूप m मात्राओं में विभाजन है। जबकि मूल एल्गोरिथ्म एक रैखिक प्रक्षेप प्रकार है, यदि इनपुट वितरण को गैर-समान माना जाता है, तो एक गैर-रेखीय विभाजन इस आदर्श को अधिक निकटता से अनुमानित करेगा। इसी तरह अंतिम सॉर्ट पुनरावर्ती फ़्लैश सॉर्ट सहित कई तकनीकों में से किसी एक का उपयोग कर सकता है। | ||
फ़्लैश सॉर्ट को जो अलग करता है वह चरण 5 है: अतिरिक्त मेमोरी के केवल एम शब्दों का उपयोग करके प्रत्येक बकेट के अवयव | फ़्लैश सॉर्ट को जो अलग करता है वह चरण 5 है: अतिरिक्त मेमोरी के केवल एम शब्दों का उपयोग करके प्रत्येक बकेट के अवयव को सही सापेक्ष क्रम में एकत्र करने के लिए एक कुशल {{math|''O''(''n'')}} इन-प्लेस एल्गोरिदम है । | ||
== मेमोरी कुशल कार्यान्वयन | == मेमोरी कुशल कार्यान्वयन == | ||
फ्लैशसॉर्ट पुनर्व्यवस्था चरण चक्रों और निश्चित बिंदुओं में संचालित होता है। अवयव "अवर्गीकृत" से प्रारंभ होते हैं फिर उन्हें सही बकेट में ले जाया जाता है और "वर्गीकृत" माना जाता है। मूल प्रक्रिया एक अवर्गीकृत अवयव को चुनना, उसकी सही बकेट खोजा जाता है, उसे वहां एक अवर्गीकृत अवयव के साथ विनिमय करना है (जो अस्तित्व में होना चाहिए, क्योंकि हमने प्रत्येक बकेट के आकार को समय से पहले गिना है), इसे वर्गीकृत के रूप में चिह्नित करें, और फिर उसी के साथ दोहराएं। अभी-अभी अवर्गीकृत अवयव का आदान-प्रदान किया गया था। अंततः, अवयव का आपस में आदान-प्रदान हो जाता है और चक्र समाप्त हो जाता है। | फ्लैशसॉर्ट पुनर्व्यवस्था चरण चक्रों और निश्चित बिंदुओं में संचालित होता है। अवयव "अवर्गीकृत" से प्रारंभ होते हैं फिर उन्हें सही बकेट में ले जाया जाता है और "वर्गीकृत" माना जाता है। मूल प्रक्रिया एक अवर्गीकृत अवयव को चुनना, उसकी सही बकेट खोजा जाता है, उसे वहां एक अवर्गीकृत अवयव के साथ विनिमय करना है (जो अस्तित्व में होना चाहिए, क्योंकि हमने प्रत्येक बकेट के आकार को समय से पहले गिना है), इसे वर्गीकृत के रूप में चिह्नित करें, और फिर उसी के साथ दोहराएं। अभी-अभी अवर्गीकृत अवयव का आदान-प्रदान किया गया था। अंततः, अवयव का आपस में आदान-प्रदान हो जाता है और चक्र समाप्त हो जाता है। | ||
| Line 30: | Line 25: | ||
प्रति बकेट दो चर के साथ इसे समझने के लिए, मान लें कि दो सारणियाँ हैं मान ले की {{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''−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''−1</sub> ≤ ''L<sub>b</sub>'' ≤ ''K<sub>b</sub>''}}. | ||
हम लूप को अपरिवर्तनीय बनाए रखते हैं कि प्रत्येक बकेट को {{mvar|L<sub>b</sub>}} द्वारा एक अवर्गीकृत उपसर्ग में विभाजित किया जाता है ({{math|''K''<sub>''b''−1</sub> < ''i'' ≤ ''L<sub>b</sub>''}} के लिए {{mvar|A<sub>i</sub>}} को अभी तक उनके लक्ष्य बकेट में स्थानांतरित नहीं किया गया है) और एक वर्गीकृत प्रत्यय ({{math|''L<sub>b</sub>'' < ''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''−1</sub>}} तक घटाया जाता है और सभी अवयव | हम लूप को अपरिवर्तनीय बनाए रखते हैं कि प्रत्येक बकेट को {{mvar|L<sub>b</sub>}} द्वारा एक अवर्गीकृत उपसर्ग में विभाजित किया जाता है ({{math|''K''<sub>''b''−1</sub> < ''i'' ≤ ''L<sub>b</sub>''}} के लिए {{mvar|A<sub>i</sub>}} को अभी तक उनके लक्ष्य बकेट में स्थानांतरित नहीं किया गया है) और एक वर्गीकृत प्रत्यय ({{math|''L<sub>b</sub>'' < ''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''−1</sub>}} तक घटाया जाता है और सभी अवयव को सही बकेट में वर्गीकृत किया जाता है। | ||
प्रत्येक समय पहली अपूर्ण रूप से वर्गीकृत बकेट {{mvar|c}} (जिसमें {{math|''K''<sub>''c''−1</sub> < ''L<sub>c</sub>''}} है) को खोजने और उस बकेट {{mvar|A<sub>i</sub>}} में पहला अवर्गीकृत अवयव लेने से प्रारंभ होता है जहां {{math|1=''i'' = ''K''<sub>''c''−1</sub> + 1}} है। (न्यूबर्ट इसे "साइकिल लीडर" कहते हैं।) {{mvar|A<sub>i</sub>}} को अस्थायी चर t में प्रतिलिपि करें और दोहराएं: | प्रत्येक समय पहली अपूर्ण रूप से वर्गीकृत बकेट {{mvar|c}} (जिसमें {{math|''K''<sub>''c''−1</sub> < ''L<sub>c</sub>''}} है) को खोजने और उस बकेट {{mvar|A<sub>i</sub>}} में पहला अवर्गीकृत अवयव लेने से प्रारंभ होता है जहां {{math|1=''i'' = ''K''<sub>''c''−1</sub> + 1}} है। (न्यूबर्ट इसे "साइकिल लीडर" कहते हैं।) {{mvar|A<sub>i</sub>}} को अस्थायी चर t में प्रतिलिपि करें और दोहराएं: | ||
| Line 45: | Line 40: | ||
यद्यपि पिछला विवरण चक्र नेताओं को खोजने के लिए {{mvar|K}} का उपयोग करता है, वास्तव में इसके बिना ऐसा करना संभव है, जिससे संपूर्ण {{mvar|m}}-शब्द सरणी को समाप्त किया जा सकता है। (वितरण पूरा होने के बाद, बकेट सीमाएँ {{mvar|L}} में पाई जा सकती हैं।) | यद्यपि पिछला विवरण चक्र नेताओं को खोजने के लिए {{mvar|K}} का उपयोग करता है, वास्तव में इसके बिना ऐसा करना संभव है, जिससे संपूर्ण {{mvar|m}}-शब्द सरणी को समाप्त किया जा सकता है। (वितरण पूरा होने के बाद, बकेट सीमाएँ {{mvar|L}} में पाई जा सकती हैं।) | ||
मान लीजिए कि हमने {{math|''i''−1}} तक के सभी अवयव | मान लीजिए कि हमने {{math|''i''−1}} तक के सभी अवयव को वर्गीकृत कर दिया है, और {{mvar|A<sub>i</sub>}} को एक संभावित नए चक्र नेता के रूप में मान रहे हैं। इसके लक्ष्य बकेट {{mvar|b}} की गणना करना आसान है। लूप इनवेरिएंट द्वारा, इसे वर्गीकृत किया जाता है यदि {{math|''L<sub>b</sub>'' < ''i'' ≤ ''K<sub>b</sub>''}}, और यदि {{mvar|i}} उस सीमा से बाहर है तो अवर्गीकृत किया जाता है। पहली असमानता का परीक्षण करना आसान है, किंतु दूसरे के लिए मान {{mvar|K<sub>b</sub>}} की आवश्यकता होती है। | ||
यह पता चलता है कि प्रेरण परिकल्पना कि {{math|''i''−1}} तक के सभी अवयव | यह पता चलता है कि प्रेरण परिकल्पना कि {{math|''i''−1}} तक के सभी अवयव को वर्गीकृत किया गया है, इसका तात्पर्य है कि {{math|''i'' ≤ ''K<sub>b</sub>''}}, इसलिए दूसरी असमानता का परीक्षण करना आवश्यक नहीं है। | ||
बकेट {{mvar|c}} पर विचार करें जो {{mvar|i}} स्थिति में आती है। अर्थात्, {{math|''K''<sub>''c''−1</sub> < ''i'' ≤ ''K<sub>c</sub>''}}. प्रेरण परिकल्पना के अनुसार, नीचे दिए गए सभी अवयव {{mvar|i}}, जिसमें {{math|''K''<sub>''c''−1</sub> < ''i''}}तक की सभी बकेट सम्मिलित हैं, पूरी तरह से वर्गीकृत हैं। अर्थात। उन बकेट में सम्मिलित कोई भी अवयव शेष सरणी में नहीं रहता है। इसलिए, यह संभव नहीं है कि {{math|''b'' < ''c''}}. | बकेट {{mvar|c}} पर विचार करें जो {{mvar|i}} स्थिति में आती है। अर्थात्, {{math|''K''<sub>''c''−1</sub> < ''i'' ≤ ''K<sub>c</sub>''}}. प्रेरण परिकल्पना के अनुसार, नीचे दिए गए सभी अवयव {{mvar|i}}, जिसमें {{math|''K''<sub>''c''−1</sub> < ''i''}}तक की सभी बकेट सम्मिलित हैं, पूरी तरह से वर्गीकृत हैं। अर्थात। उन बकेट में सम्मिलित कोई भी अवयव शेष सरणी में नहीं रहता है। इसलिए, यह संभव नहीं है कि {{math|''b'' < ''c''}}. | ||
Revision as of 11:27, 14 July 2023
फ्लैशसॉर्ट एक वितरण सॉर्टिंग एल्गोरिदम है जो समान रूप से वितरित डेटा सेट और अपेक्षाकृत कम अतिरिक्त मेमोरी आवश्यकता के लिए रैखिक कम्प्यूटेशनल जटिलता O(n) दिखाता है। मूल कार्य 1998 में कार्ल-डिट्रिच न्यूबर्ट द्वारा प्रकाशित किया गया था।[1]
संकल्पना
फ्लैशसॉर्ट हिस्टोग्राम सॉर्ट का एक कुशल इन-प्लेस कार्यान्वयन है, जो स्वयं एक प्रकार का बकेट सॉर्ट है। यह प्रत्येक n इनपुट अवयव को m बकेट में से एक को निर्दिष्ट करता है, बकेट को सही क्रम में रखने के लिए इनपुट को कुशलतापूर्वक पुनर्व्यवस्थित करता है, फिर प्रत्येक बकेट को सॉर्ट करता है। मूल एल्गोरिदम एक इनपुट सरणी A को निम्नानुसार सॉर्ट करता है:
- इनपुट पर पहले पास या प्राथमिक ज्ञान का उपयोग करके न्यूनतम और अधिकतम सॉर्ट कुंजी खोजे ।
- रेंज [Amin, Amax] को रैखिक रूप से m बकेट में विभाजित करें।
- प्रत्येक बकेट में गिरने वाले Ai अवयव की संख्या गिनते हुए, इनपुट पर एक पास बनाते है। (न्यूबर्ट बकेट को "वर्ग" और उनकी बकेट में अवयव के असाइनमेंट को "वर्गीकरण" कहते हैं।)
- प्रत्येक बकेट में अवयव की संख्या को उपसर्ग योग में बदलें, जहां Lb बकेट b या उससे कम में अवयव Ai की संख्या है। (L0 = 0 और Lm = n.)
- प्रत्येक बकेट b के सभी अवयव के इनपुट को पुनर्व्यवस्थित करें, स्थिति Ai में संग्रहीत किया जाता है जहां Lb−1 < i ≤ Lb।
- सम्मिलन सॉर्ट का उपयोग करके प्रत्येक बकेट को सॉर्ट करें।
चरण 1-3 और 6 किसी भी बकेट सॉर्ट के लिए सामान्य हैं, और बकेट सॉर्ट के लिए सामान्य तकनीकों का उपयोग करके इसमें सुधार किया जा सकता है। विशेष रूप से, लक्ष्य यह है कि बकेट लगभग समान आकार (प्रत्येकn/m अवयव ) की हों[1] जिसका आदर्श रूप m मात्राओं में विभाजन है। जबकि मूल एल्गोरिथ्म एक रैखिक प्रक्षेप प्रकार है, यदि इनपुट वितरण को गैर-समान माना जाता है, तो एक गैर-रेखीय विभाजन इस आदर्श को अधिक निकटता से अनुमानित करेगा। इसी तरह अंतिम सॉर्ट पुनरावर्ती फ़्लैश सॉर्ट सहित कई तकनीकों में से किसी एक का उपयोग कर सकता है।
फ़्लैश सॉर्ट को जो अलग करता है वह चरण 5 है: अतिरिक्त मेमोरी के केवल एम शब्दों का उपयोग करके प्रत्येक बकेट के अवयव को सही सापेक्ष क्रम में एकत्र करने के लिए एक कुशल O(n) इन-प्लेस एल्गोरिदम है ।
मेमोरी कुशल कार्यान्वयन
फ्लैशसॉर्ट पुनर्व्यवस्था चरण चक्रों और निश्चित बिंदुओं में संचालित होता है। अवयव "अवर्गीकृत" से प्रारंभ होते हैं फिर उन्हें सही बकेट में ले जाया जाता है और "वर्गीकृत" माना जाता है। मूल प्रक्रिया एक अवर्गीकृत अवयव को चुनना, उसकी सही बकेट खोजा जाता है, उसे वहां एक अवर्गीकृत अवयव के साथ विनिमय करना है (जो अस्तित्व में होना चाहिए, क्योंकि हमने प्रत्येक बकेट के आकार को समय से पहले गिना है), इसे वर्गीकृत के रूप में चिह्नित करें, और फिर उसी के साथ दोहराएं। अभी-अभी अवर्गीकृत अवयव का आदान-प्रदान किया गया था। अंततः, अवयव का आपस में आदान-प्रदान हो जाता है और चक्र समाप्त हो जाता है।
प्रति बकेट दो (शब्द-आकार) चर का उपयोग करके विवरण को समझना आसान है। चतुर भाग उन चरों में से एक को समाप्त करना है, जिससे दोगुनी बकेट का उपयोग किया जा सकता है और इसलिए अंतिम O(n2) सॉर्टिंग पर आधा समय खर्च किया जाता है।
प्रति बकेट दो चर के साथ इसे समझने के लिए, मान लें कि दो सारणियाँ हैं मान ले की m अतिरिक्त शब्द: Kb बकेट की (निश्चित) ऊपरी सीमा है b (और K0 = 0), जबकि Lb बकेट b में एक (चलने योग्य) सूचकांक है इसलिए Kb−1 ≤ Lb ≤ Kb.
हम लूप को अपरिवर्तनीय बनाए रखते हैं कि प्रत्येक बकेट को Lb द्वारा एक अवर्गीकृत उपसर्ग में विभाजित किया जाता है (Kb−1 < i ≤ Lb के लिए Ai को अभी तक उनके लक्ष्य बकेट में स्थानांतरित नहीं किया गया है) और एक वर्गीकृत प्रत्यय (Lb < i ≤ Kb के लिए Ai सभी हैं) सही बकेट में और दोबारा नहीं ले जाया जाएगा)। प्रारंभ में Lb = Kb और सभी अवयव अवर्गीकृत हैं। जैसे-जैसे छँटाई आगे बढ़ती है,Lb को सभी b के लिए Lb = Kb−1 तक घटाया जाता है और सभी अवयव को सही बकेट में वर्गीकृत किया जाता है।
प्रत्येक समय पहली अपूर्ण रूप से वर्गीकृत बकेट c (जिसमें Kc−1 < Lc है) को खोजने और उस बकेट Ai में पहला अवर्गीकृत अवयव लेने से प्रारंभ होता है जहां i = Kc−1 + 1 है। (न्यूबर्ट इसे "साइकिल लीडर" कहते हैं।) Ai को अस्थायी चर t में प्रतिलिपि करें और दोहराएं:
- उस बकेट b की गणना करें जिससे t संबंधित है।
- मान लीजिए j = Lb वह स्थान है जहाँ t संग्रहीत किया जाएगा।
- t को Aj के साथ बदलें, अथार्त पिछले मान Aj को प्राप्त करते समय t को Aj में संग्रहीत करें जिससे Aj विस्थापित हो जाए।
- इस तथ्य को प्रतिबिंबित करने के लिए Lb घटाएं कि Aj को अब सही रूप से वर्गीकृत किया गया है।
- यदि j ≠ i, तो इस लूप को नए t के साथ पुनरारंभ करें।
- यदि j = i, तो यह दौर समाप्त हो गया है और एक नया पहला अवर्गीकृत अवयव Ai खोजे जाते है।
- जब कोई अवर्गीकृत अवयव नहीं रह जाते हैं, तो बकेट में वितरण पूरा हो जाता है।
जब इस तरह से प्रति बकेट दो चर के साथ कार्यान्वित किया जाता है, तो प्रत्येक समय के प्रारंभिक बिंदु का विकल्प i वास्तव में इच्छानुसार है; किसी भी अवर्गीकृत अवयव का उपयोग साइकिल लीडर के रूप में किया जा सकता है। एकमात्र आवश्यकता यह है कि साइकिल लीडरों को कुशलतापूर्वक पाया जा सकता है।
यद्यपि पिछला विवरण चक्र नेताओं को खोजने के लिए K का उपयोग करता है, वास्तव में इसके बिना ऐसा करना संभव है, जिससे संपूर्ण m-शब्द सरणी को समाप्त किया जा सकता है। (वितरण पूरा होने के बाद, बकेट सीमाएँ L में पाई जा सकती हैं।)
मान लीजिए कि हमने i−1 तक के सभी अवयव को वर्गीकृत कर दिया है, और Ai को एक संभावित नए चक्र नेता के रूप में मान रहे हैं। इसके लक्ष्य बकेट b की गणना करना आसान है। लूप इनवेरिएंट द्वारा, इसे वर्गीकृत किया जाता है यदि Lb < i ≤ Kb, और यदि i उस सीमा से बाहर है तो अवर्गीकृत किया जाता है। पहली असमानता का परीक्षण करना आसान है, किंतु दूसरे के लिए मान Kb की आवश्यकता होती है।
यह पता चलता है कि प्रेरण परिकल्पना कि i−1 तक के सभी अवयव को वर्गीकृत किया गया है, इसका तात्पर्य है कि i ≤ Kb, इसलिए दूसरी असमानता का परीक्षण करना आवश्यक नहीं है।
बकेट c पर विचार करें जो i स्थिति में आती है। अर्थात्, Kc−1 < i ≤ Kc. प्रेरण परिकल्पना के अनुसार, नीचे दिए गए सभी अवयव i, जिसमें Kc−1 < iतक की सभी बकेट सम्मिलित हैं, पूरी तरह से वर्गीकृत हैं। अर्थात। उन बकेट में सम्मिलित कोई भी अवयव शेष सरणी में नहीं रहता है। इसलिए, यह संभव नहीं है कि b < c.
एकमात्र शेष स्थिति b ≥ c है, जिसका अर्थ है Kb ≥ Kc ≥ i, Q.E.D.
इसे सम्मिलित करते हुए, फ्लैशसॉर्ट वितरण एल्गोरिदम ऊपर बताए अनुसार L से प्रारंभ होता है और i = 1. फिर आगे बढ़ें:[1][2]
- यदिi > n तो वितरण पूरा हो गया है।
- Ai को देखते हुए, उस बकेट b की गणना करें जिससे वह संबंधित है।
- यदि i ≤ Lb, तो Ai अवर्गीकृत है। इसे एक अस्थायी चर t प्रतिलिपि करें और:
- मान लीजिए j = Lb वह स्थान है जहाँ t संग्रहीत किया जाएगा।
- t को Aj के साथ बदलें, अर्थात पिछले मान Ajको प्राप्त करते समय t को Ajमें संग्रहीत करें जिससे Ajविस्थापित हो जाए।
- इस तथ्य को प्रतिबिंबित करने के लिए Lb घटाएं कि Ajको अब सही रूप से वर्गीकृत किया गया है।
- यदि j ≠ i, तो उस बकेट b की गणना करें जिससे t संबंधित है और इस (आंतरिक) लूप को नए t के साथ पुनरारंभ करें।
- Ai अब सही रूप से वर्गीकृत किया गया है। वेतन वृद्धि i और (बाहरी) लूप को पुनरारंभ करें।
मेमोरी को सहेजते समय, फ्लैशसॉर्ट का हानि यह है कि यह पहले से ही वर्गीकृत कई अवयव के लिए बकेट की पुन: गणना करता है। यह पहले से ही प्रति अवयव दो बार किया जाता है (एक बार बकेट -गिनती चरण के समय और दूसरी बार प्रत्येक अवयव को स्थानांतरित करते समय), किंतु पहले अवर्गीकृत अवयव की खोज के लिए अधिकांश अवयव के लिए तीसरी गणना की आवश्यकता होती है। यह मूल्यवान हो सकता है यदि बकेट को सरल रैखिक प्रक्षेप की तुलना में अधिक जटिल सूत्र का उपयोग करके निर्दिष्ट किया जाता है। एक प्रकार चक्र लीडर के रूप में एक अधूरी बकेट में अंतिम अवर्गीकृत तत्व को लेकर गणनाओं की संख्या को लगभग 3n से घटाकर अधिकतम 2n + m − 1 कर देता है:
- पहले अपूर्ण-वर्गीकृत बकेट की पहचान करने वाला एक वेरिएबल c बनाए रखें। आरंभ करने के लिए मान लीजिए c = 1 है, और जब c > m वितरण पूरा हो जाता है।
- चलो i = Lc. यदि i = Lc−1 है, तो c बढ़ाएँ और इस लूप को पुनरारंभ करें। (L0 = 0.)
- उस बकेट b की गणना करें जिससे Ai संबंधित है।
- यदि b < c, तो Lc = Kc−1 और हमने बकेट c का काम पूरा कर लिया है। c बढ़ाएँ और इस लूप को पुनरारंभ करें।
- यदि b = c है, तो वर्गीकरण तुच्छ है। Lc घटाएं और इस लूप को पुनरारंभ करें।
- यदि b > c, तो Ai अवर्गीकृत है। पिछले स्थिति की तरह ही वर्गीकरण लूप निष्पादित करें और फिर इस लूप को पुनरारंभ करें।
अधिकांश अवयव की बकेट की गणना केवल दो बार की जाती है, प्रत्येक बकेट में अंतिम अवयव को छोड़कर, जिसका उपयोग निम्नलिखित बकेट के पूरा होने का पता लगाने के लिए किया जाता है। अवर्गीकृत अवयव की गिनती बनाए रखने और शून्य तक पहुंचने पर रोककर थोड़ी और कमी प्राप्त की जा सकती है।
प्रदर्शन
एकमात्र अतिरिक्त मेमोरी आवश्यकताएं बकेट सीमा और उपयोग किए गए अन्य चर की निरंतर संख्या को संग्रहीत करने के लिए सहायक वेक्टर L हैं। इसके अतिरिक्त , प्रत्येक अवयव को केवल एक बार स्थानांतरित किया जाता है (एक अस्थायी बफर के माध्यम से, इसलिए दो चाल संचालन)। चूँकि, यह मेमोरी दक्षता इस हानि के साथ आती है कि सरणी को यादृच्छिक रूप से एक्सेस किया जाता है, इसलिए संपूर्ण सरणी से छोटे डेटा कैश का लाभ नहीं उठाया जा सकता है।
सभी बकेट प्रकारों की तरह, प्रदर्शन गंभीर रूप से बकेट के संतुलन पर निर्भर करता है। संतुलित डेटा सेट के आदर्श स्थिति में, प्रत्येक बकेट लगभग समान आकार की होगी। यदि इनपुट आकार n में बकेट की संख्या m रैखिक है, तो प्रत्येक बकेट का एक स्थिर आकार होता है, इसलिए एक एकल बकेट को O(n2) एल्गोरिदम जैसे प्रविष्टि सॉर्ट के साथ सॉर्ट करने में जटिलता O(12) = O(1) होती है। इसलिए अंतिम प्रविष्टि प्रकार का चलने का समय m ⋅ O(1) = O(m) = O(n) है।
m के लिए एक मान चुनना, बकेट की संख्या, तत्वों को वर्गीकृत करने में लगने वाला समय (उच्च m) और अंतिम प्रविष्टि सॉर्ट चरण (कम m) में लगने वाला समय कम हो जाता है। उदाहरण के लिए, यदि m को √n के आनुपातिक रूप से चुना गया है, तो अंतिम प्रविष्टि प्रकार का चलने का समय m ⋅ O(√n2) = O(n3/2) है।
सबसे व्यर्थ स्थिति में जहां लगभग सभी तत्व कुछ बकेट में होते हैं, एल्गोरिदम की जटिलता अंतिम बकेट-सॉर्टिंग विधि के प्रदर्शन से सीमित होती है, इसलिए यह O(n2) तक घट जाती है। एल्गोरिदम की विविधताएं एक निश्चित आकार सीमा से अधिक की बकेट पर उत्तम प्रदर्शन करने वाले प्रकारों जैसे क्विकसॉर्ट या रिकर्सिव फ्लैशसॉर्ट का उपयोग करके सबसे व्यर्थ स्थिति के प्रदर्शन में सुधार करती हैं।।[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.
