फ्लैशसॉर्ट

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

संकल्पना

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

1. इनपुट पर पहले पास या प्राथमिक ज्ञान का उपयोग करके, न्यूनतम और अधिकतम सॉर्ट कुंजी ढूंढें।
2. रेंज को रैखिक रूप से विभाजित करें [A_min, A_max] में m बाल्टियाँ।
3. तत्वों की संख्या गिनते हुए, इनपुट पर एक पास बनाएं A_i जो प्रत्येक बाल्टी में गिरती है। (न्यूबर्ट बकेट क्लासेस और तत्वों के असाइनमेंट को उनके बकेट वर्गीकरण कहते हैं।)
4. प्रत्येक बकेट में तत्वों की संख्या को उपसर्ग योग में बदलें, जहां L_bतत्वों की संख्या है A_i बाल्टी में b या कम। (L₀ = 0 और L_m = n.)
5. प्रत्येक बकेट के सभी तत्वों में इनपुट को पुनर्व्यवस्थित करें b पदों पर संग्रहीत हैं A_i कहाँ L_b−1 < i ≤ L_b.
6. सम्मिलन सॉर्ट का उपयोग करके प्रत्येक बकेट को सॉर्ट करें।

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

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

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

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

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

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

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

प्रत्येक दौर की शुरुआत पहली अपूर्ण रूप से वर्गीकृत बाल्टी को खोजने से होती है 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, अर्थात। इकट्ठा करना 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 ≤ K_b, और अवर्गीकृत यदि i उस सीमा से बाहर है. पहली असमानता (गणित) का परीक्षण करना आसान है, लेकिन दूसरे के लिए मूल्य की आवश्यकता होती है K_b.

इससे पता चलता है कि प्रेरण परिकल्पना सभी तत्वों तक पहुँचती है i−1 वर्गीकृत किये जाने का तात्पर्य यह है कि i ≤ K_b, इसलिए दूसरी असमानता का परीक्षण करना आवश्यक नहीं है।

बाल्टी पर विचार करें c कौन सी स्थिति i अंदर गिरा। वह है, K_c−1 < i ≤ K_c. प्रेरण परिकल्पना के अनुसार, नीचे दिए गए सभी तत्व i, जिसमें तक की सभी बकेट शामिल हैं K_c−1 < i, पूर्णतः वर्गीकृत हैं। अर्थात। उन बकेट में शामिल कोई भी तत्व शेष सरणी में नहीं रहता है। इसलिए ऐसा संभव नहीं है b < c.

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

इसे शामिल करते हुए, फ्लैशसॉर्ट वितरण एल्गोरिदम शुरू होता है L जैसा कि ऊपर वर्णित है और i = 1. फिर आगे बढ़ें:

• अगर i > n, वितरण पूर्ण हो गया है।
• दिया गया A_i, बाल्टी की गणना करें b जिससे यह संबंधित है।
• अगर i ≤ L_b, तब A_i अवर्गीकृत है. इसे एक अस्थायी चर की प्रतिलिपि बनाएँ t और:
  • होने देना j = L_b वह स्थान हो जहां t संग्रहित किया जाएगा.
  • अदला-बदली t साथ A_j, अर्थात। इकट्ठा करना t में A_j पिछला मान लाते समय A_j जिससे विस्थापित हो गया।
  • कमी L_b इस तथ्य को प्रतिबिंबित करने के लिए A_j अब सही ढंग से वर्गीकृत किया गया है।
  • अगर j ≠ i, बाल्टी की गणना करें b किसको t संबंधित है और इस (आंतरिक) लूप को नए के साथ पुनः आरंभ करें t.
• A_i अब सही ढंग से वर्गीकृत किया गया है। वेतन वृद्धि i और (बाहरी) लूप को पुनरारंभ करें।

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

• एक वैरिएबल बनाए रखें c पहली अपूर्ण-वर्गीकृत बाल्टी की पहचान करना। होने देना c = 1 शुरू करने के लिए, और कब c > m, वितरण पूर्ण हो गया है।
• होने देना i = L_c. अगर i = L_c−1, वृद्धि c और इस लूप को पुनरारंभ करें। (L₀ = 0.)
• बाल्टी की गणना करें b किसको A_i का है.
• अगर b < c, तब L_c = K_c−1 और हमारा बाल्टी से काम पूरा हो गया c. वेतन वृद्धि c और इस लूप को पुनरारंभ करें।
• अगर b = c, वर्गीकरण तुच्छ है. घटती L_c और इस लूप को पुनरारंभ करें।
• अगर b > c, तब A_i अवर्गीकृत है. पिछले मामले की तरह ही वर्गीकरण लूप निष्पादित करें, फिर इस लूप को पुनरारंभ करें।

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

प्रदर्शन

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

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

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

सबसे खराब स्थिति में जहां लगभग सभी तत्व कुछ बकेट में होते हैं, एल्गोरिदम की जटिलता अंतिम बकेट-सॉर्टिंग विधि के प्रदर्शन से सीमित होती है, इसलिए इसमें गिरावट आती है O(n²). एल्गोरिदम की विविधताएं एक निश्चित आकार सीमा से अधिक की बाल्टियों पर बेहतर प्रदर्शन करने वाले प्रकारों जैसे जल्दी से सुलझाएं या रिकर्सिव फ्लैशसॉर्ट का उपयोग करके सबसे खराब स्थिति के प्रदर्शन में सुधार करती हैं। के लिए m = 0.1 n समान रूप से वितरित यादृच्छिक डेटा के साथ, फ्लैशसॉर्ट सभी के लिए ढेर बनाएं और छांटें से तेज है n और क्विकसॉर्ट से तेज़ n > 80. यह क्विकसॉर्ट की तुलना में लगभग दोगुना तेज़ हो जाता है n = 10000. ध्यान दें कि ये माप 1990 के दशक के अंत में लिए गए थे, जब मेमोरी पदानुक्रम कैशिंग पर बहुत कम निर्भर था। फ्लैशसॉर्ट अपनी वर्गीकरण प्रक्रिया में जो यथास्थान क्रमपरिवर्तन करता है, उसके कारण फ्लैशसॉर्ट स्थिर सॉर्ट#स्थिरता नहीं है। यदि स्थिरता की आवश्यकता है, तो दूसरी सरणी का उपयोग करना संभव है ताकि तत्वों को क्रमिक रूप से वर्गीकृत किया जा सके। हालाँकि, इस मामले में, एल्गोरिदम की आवश्यकता होगी O(n) अतिरिक्त मेमोरी.

यह भी देखें

• सॉर्टिंग के बजाय खोज एल्गोरिदम के लिए वस्तुओं के वितरण का उपयोग करके अंतर्वेशन खोज

बाहरी संबंध

• Implementations of Randomized Sorting on Large Parallel Machines (1992)
• Implementation of Parallel Algorithms (1992)
• Visualization of Flashsort