👨‍🚀 🔥 🐾 वितरण द्वारा एक और प्रकार 👩🏻‍🎨 🗝️ 👈🏿

जब यह कुशल छँटाई एल्गोरिदम की बात आती है, तो एक एरेडिट हैब्राइज़र तुरंत सामने आने वाले " त्वरित सॉर्ट ", नए-फंसे हुए " टिम सॉर्ट ", पौराणिक " मर्ज सॉर्ट " और यहां तक कि पेचीदा " आत्मनिरीक्षण " को भी याद करेगा।

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

यह FlashSort है , जो समान रूप से वितरित डेटा के साथ बहुत बड़ी सरणियों को संभालता है।

1998 में विधि जर्मन वैज्ञानिक कार्ल-डिट्रिच न्युबर्ट द्वारा पेश की गई थी। उनका वैज्ञानिक कार्य एल्गोरिदम के सिद्धांत के प्रति इतना समर्पित नहीं है जितना कि ठोस अवस्था भौतिकी, जैव भौतिकी प्रणाली, प्राथमिक कण भौतिकी। प्रयोगों के परिणामों का विश्लेषण करते हुए, न्यूबर्ट इस निष्कर्ष पर पहुंचे कि सांख्यिकीय डेटा के बड़े सरणियों को क्रमबद्धता के लिए काफी तार्किक है, संभाव्यता सिद्धांत का सहारा लेना।

दिल

ऑपरेशन के सिद्धांत को एक विशिष्ट उदाहरण के साथ समझाना आसान है।

मान लीजिए कि एन तत्वों का एक बड़ा सरणी है, जिनका मान 1 से 100 तक है । यदि हम 50 के मान के साथ किसी तत्व को पूरा करते हैं, तो हम यथोचित मान लेते हैं कि इसका सही स्थान सरणी के बीच में है। स्थिति अन्य तत्वों के साथ समान है: 5 , शायद, संरचना की शुरुआत के करीब होना चाहिए, 95 इसे लगभग अंत तक धकेलना उचित है। इस तरह के लापरवाह जोड़तोड़ के परिणामस्वरूप, हम जल्दी से एक लगभग सॉर्ट किए गए सरणी प्राप्त करते हैं ।

जल्दी में तत्वों को हाथापाई करने के बाद, यह कुछ विधि लागू करने के लिए बनी हुई है जो जल्दी से अव्यवस्थित एक को पुन: व्यवस्थित करती है ( आवेषण द्वारा छांटना काफी उपयुक्त है)।

Matan

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

यदि हम कक्षाओं की संख्या के लिए मीटर लेते हैं, और सरणी में न्यूनतम ए _{न्यूनतम} और अधिकतम ए _{अधिकतम} तत्व भी ज्ञात हैं, तो तत्व ए _i के वर्ग संख्या _की गणना निम्न सूत्र द्वारा की जाती है:

प्रायिकता सिद्धांत के दृष्टिकोण से, क्लास K हमारे वितरण मॉडल में तत्व ए _i की जगह को इंगित करने वाले एक मात्रात्मक से अधिक कुछ भी नहीं है।

अभिव्यक्ति में वर्ग कोष्ठक का अर्थ पूर्णांक भाग है। इस प्रकार कक्षाएं 1 से m तक बदल दी जाएंगी। अतिरिक्त सरणी Q [ 1..m ] में, संबंधित वर्ग के मुख्य सरणी से तत्वों की संख्या Q [ K ] की स्थिति में दर्ज की गई है।

फिर, एक अतिरिक्त सरणी का उपयोग करके, हम मुख्य सरणी के तत्वों को पुनर्वितरित करते हैं, उन्हें लगभग उनके स्थानों में डालते हैं। एल्गोरिथम की बारीकियों - नीचे दिए गए जावा प्रोग्राम के कोड में।

दृश्य

अवधि 2 मिनट से अधिक। यह स्पष्ट हो जाएगा कि क्यों छंटाई को "टिमटिमा" करार दिया गया है।

YouTube संस्करण

समय दक्षता

जैसा कि पहले ही उल्लेख किया गया है, एल्गोरिथ्म समान रूप से वितरित डेटा के साथ बड़े सरणियों पर बहुत कुशल है। इस मामले में, O (n) की औसत समय जटिलता के साथ FlashSort , QuickSort और अन्य कुशल सॉर्टिंग विधियों दोनों से काफी आगे है।

अन्य स्थितियों में, चीजें इतनी शानदार नहीं हैं। छोटे सरणियों पर, डेटा के असमान रूप से वितरित डेटा के साथ लंबे सरणियों पर, "टिमटिमा छँटाई" हालांकि स्वीकार्य है, लेकिन बहुत अधिक मामूली परिणाम दिखाता है।

मुख्य एल्गोरिथ्म को अपूर्ण रूप से आदेशित सरणियों पर लागू करने का कोई मतलब नहीं है, आवेषण द्वारा तुरंत छंटनी करना आसान है। FlashSort के लिए एक लगभग सॉर्ट किया गया सरणी एक पतित मामला है, और विशेष रूप से असफल स्थितियों में, सबसे खराब समय मनाया जाता है, और मेरे पास O (n ² ) जटिलता है।

मेमोरी क्षमता

स्मृति पर विधि बहुत मांग नहीं है, हालांकि इसके लिए नए सरणी के लिए संसाधनों की आवश्यकता होती है, तत्वों की संख्या जिसमें कक्षाएं होती हैं। सवाल बहुत प्रासंगिक है: क्या मीटर लेना है? अधिक वर्ग - बेहतर वितरण होगा, लेकिन अतिरिक्त मेमोरी के रूप में कीमत भी अधिक होगी। ज्यादातर मामलों में, सूत्र द्वारा एक स्वीकार्य मूल्य / गुणवत्ता अनुपात दिया जाता है

एम m 0.42 एन ,

आनुभविक रूप से न्यूबर्ट द्वारा व्युत्पन्न।

यदि मुख्य सरणी के तत्वों के संभावित मानों की सीमा पर्याप्त रूप से छोटी है, तो न्यूनतम और अधिकतम तत्वों के बीच पूर्णांक दूरी लेने के लिए मीटर संभव है (और यहां तक कि वांछनीय)। ऐसे मामलों में, "1 मान = 1 वर्ग" की स्थिति के अधीन, समय के अनुसार छंटनी की गति थोड़ा अतिरिक्त मेमोरी के साथ सबसे अच्छा परिणाम ओ (एन) तक पहुंचती है।

कार्यान्वयन

जावा में FlashSort।

import java.util.Arrays; public class FlashSortAlgorithm extends SortAlgorithm { void sort(int[] a) throws Exception { FlashSort(a); // FlashSort InsertionSort(a); //   } //FlashSort,    //   private void FlashSort(int [] a) throws Exception { int n = a.length; //  int m = n * 0.42; //  int [] l = new int[m]; //  int i = 0, j = 0, k = 0; //   int anmin = a[0]; //  int nmax = 0; //   //     for (i = 1; i < n; i++) { if (a[i] < anmin) anmin = a[i]; if (a[i] > a[nmax]) nmax = i; } // = ?   //   . // ,  ! if (anmin == a[nmax]) return; //   double c1 = ((double) m - 1) / (a[nmax] - anmin); //   //    - //     for (i = 0; i < n; i++) { k = (int) (c1 * (a[i] - anmin)); l[k]++; } //     //(  2-)   . //      //        //     for (k = 1; k < m; k++){ l[k] += l[k - 1]; } //        //         //       int hold = a[nmax]; a[nmax] = a[0]; a[0] = hold; //  // ,  //     int nmove = 0; // ,      //      ""  int flash; //   //  ,    //  j = 0; //    //      1..m-1 k = m - 1; while (nmove < n - 1) { while (j > (l[k] - 1)) { j++; k = (int) (c1 * (a[j] - anmin)); } flash = a[j]; while (!(j == l[k])) { k = (int) (c1 * (flash - anmin)); hold = a[l[k] - 1]; a[l[k] - 1] = flash; flash = hold; l[k]--; nmove++; } } } //    //     FlashSort private void InsertionSort(int [] a) throws Exception { int i, j, hold; for (i=a.length-3; i>=0; i--) { if (a[i+1] < a[i]) { hold = a[i]; j=i; while (a[j+1] < hold) { a[j] = a[j+1]; j++; } a[j] = hold; } } } }

कोड यहाँ से लिया गया है , मेरी टिप्पणियाँ।
विभिन्न PLs (Ada, C, Basic, Fort, Fortran, Java, Pascal) में कार्यान्वयन का संग्रह प्रोफेसर की वेबसाइट पर पाया जा सकता है।

एल्गोरिदम के लक्षण

नाम	FlashSort (झिलमिलाहट छँटाई; चमकती छँटाई; चमकती छँटाई)
लेखक	कार्ल-डाइटरिक न्यूबर्ट
प्रकाशन का वर्ष	1998
वर्ग	वितरण क्रमबद्ध करें
स्थिरता	अस्थिर
तुलना	कोई तुलना नहीं
समय की जटिलता	सबसे खराब	ओ (एन ² )
	मध्यम	O (n + m)
	सबसे अच्छा	ओ (एन)
स्मृति कठिनाई	केवल	O (n + m)
स्मृति कठिनाई	अतिरिक्त डेटा	ओ (एम)

संदर्भ

अंग्रेजी विकिपीडिया पर फ्लैशशॉट
कार्ल-डिट्रीच न्युबर्ट, व्यक्तिगत वेबसाइट।
FlashSort पर Dr. डोब की पत्रिका
जावा विज़ुअलाइज़ेशन

वितरण द्वारा एक और प्रकार

दिल