🦍 ☀️ 👨‍👨‍👦 लाइब्रेरी सॉर्ट 👩🏻‍💼 🈴 👨🏽‍🏭

एक रिवर्स-ऑर्डर की गई सरणी लें और इसे सरल आवेषण के साथ छंटनी पर लागू करें।

देखें कि अगले तत्व को किस क्रेक में डाला गया है। इसके लिए, आपको प्रविष्टि स्थान को खाली करने की आवश्यकता है, जिसके कारण आपको पहले से सम्मिलित सभी तत्वों को स्थानांतरित करना होगा।

और कितना अच्छा होगा यदि पहले से डाले गए तत्वों के बीच खाली स्थान थे! तब किसी को केवल एक डालने के लिए तत्वों की पंक्तियों को खींचना नहीं होगा।

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

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

एल्गोरिथ्म

1. एक खाली सहायक सरणी बनाएं, मुख्य एक से कई गुना बड़ा।
2. अगले तत्व के लिए, हम सहायक सरणी में सम्मिलन स्थान की तलाश करते हैं।
- 2.1। यदि आपको सम्मिलित करने के लिए जगह मिलती है, तो आइटम को स्थानांतरित करें और चरण 2 पर लौटें।
- 2.2। यदि सम्मिलन के लिए कोई स्थान नहीं है, तो सहायक सरणी को फिर से संतुलित करें और बिंदु 2 पर लौटें।
3. सभी तत्वों को संसाधित करने के बाद, उन्हें वापस मुख्य सरणी में स्थानांतरित करें।

पहली नज़र में, ऐसा लगता है कि छंटाई आसान और सरल है। इस भ्रम को दूर करने के लिए, हम एल्गोरिथ्म के प्रमुख बिंदुओं पर अधिक विस्तार से विचार करते हैं।

सहायक सरणी आकार

जबकि कोई स्थापित राय नहीं है, सहायक सरणी मुख्य से कितनी बार बड़ी होनी चाहिए।

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

यदि हमने तय किया कि सहायक सरणी मुख्य से कितनी बार बड़ी है, तो इसके लिए तत्वों की सटीक संख्या निर्धारित करने का सूत्र निम्नानुसार है:

NewSize = S × (आकार + 1) - 1

NewSize - सहायक सरणी में तत्वों की संख्या
times - सहायक सरणी मुख्य से कितनी बार बड़ी है
आकार - मुख्य सरणी में तत्वों की संख्या

यदि हम बस एक कारक द्वारा आकार को गुणा करते हैं: NewSize = Size × then, तो समान वितरण के लिए हमारे पास of - 1 टुकड़े की मात्रा में पर्याप्त सेल नहीं होंगे। यही है, उन्हें समान रूप से व्यवस्थित करना संभव है, लेकिन या तो पहले भरा हुआ सेल या अंतिम सहायक सरणी के किनारे के करीब स्थित होगा। और हमें सभी पक्षों से आरक्षित होने के लिए भरे हुए कक्षों में खाली स्थानों की आवश्यकता है - पहले तत्व से पहले और आखिरी के बाद।

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

सहायक सरणी में सम्मिलन स्थान खोजें

बेशक, यहां आपको एक द्विआधारी खोज की आवश्यकता है। हालांकि, क्लासिक कार्यान्वयन हमारे लिए काम नहीं करेगा।

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

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

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

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

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

पुनर्वसन का प्रबंध करें

बाइनरी खोज इस छँटाई में लागू करने के लिए सबसे मुश्किल काम नहीं है। अभी भी असंतुलन है।

जब सम्मिलन के लिए कोई स्थान नहीं है (समान तत्व पाए गए थे, लेकिन उनके बीच कोई मुफ्त कोशिकाएं नहीं थीं), तो आपको सहायक सरणी को हिलाए जाने की आवश्यकता है ताकि सम्मिलन स्थान मुक्त हो जाए। सरणी का यह हिलाना पुनर्संतुलन है।

इसके अलावा, पुनर्संतुलन स्थानीय या पूर्ण है ।

स्थानीय पुनर्संतुलन

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

संभावित बारीकियां हैं। उदाहरण के लिए, निकटतम रिक्त स्थान की तलाश के लिए कौन सा रास्ता है? स्थिति से बचने के लिए जब एक पारी असंभव है (यानी, अगर किसी पक्ष में सभी कोशिकाओं को सरणी के बहुत किनारे पर कब्जा कर लिया जाता है), तो आप सरणी के मध्य के सापेक्ष सम्मिलन बिंदु की स्थिति पर ध्यान केंद्रित कर सकते हैं। यदि आपको सरणी के बाईं ओर सम्मिलित करने की आवश्यकता है, तो दाएं पर स्थानांतरित करें, यदि दाईं ओर - बाईं ओर। यदि If ε 2, तो यह दृष्टिकोण उस स्थिति को समाप्त कर देता है जिसमें एक बदलाव असंभव है (क्योंकि सहायक सरणी के आधे हिस्से में सभी तत्वों के लिए पर्याप्त जगह से अधिक है)।

एल्गोरिथ्म की लेखक की व्याख्या में, स्थानीय असंतुलन निहित है।

पूर्ण रीबैलेंसिंग

स्थानीय के लिए एक दिलचस्प विकल्प पूर्ण असंतुलन है। यही है, सहायक सरणी में, सभी उपलब्ध तत्वों को स्थानांतरित करें ताकि उनके बीच एक ही स्थान हो (लगभग)।

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

आइए जानें कि कैसे पूरी तरह से असंतुलन हो सकता है।

पहले आपको गणना करने की आवश्यकता है कि सहायक सरणी में प्रत्येक तत्व के लिए हम कितने अधिकतम सेल आवंटित कर सकते हैं। यह याद रखना चाहिए कि खाली कोशिकाओं को पहले से पहले और अंतिम भरे हुए सेल के बाद दोनों होना चाहिए। सूत्र है:

एम - कोशिकाओं की संख्या जो प्रत्येक तत्व को आवंटित की जा सकती है
NewSize - सहायक सरणी का आकार
गणना - सहायक सरणी में गैर-खाली तत्वों की वर्तमान संख्या

इस अंश को एक पूर्णांक मान (यानी गोल नीचे) में घटाया जाना चाहिए। यह सूत्र से स्पष्ट है कि अधिक तत्व पहले से ही सहायक सरणी में स्थानांतरित किए जाते हैं, कम कोशिकाएं हम प्रत्येक तत्व के पड़ोस के लिए चुन सकते हैं।

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

न्यूपोस = संख्या × एम

न्यूपोस - रीबैलेंसिंग के बाद नई आइटम स्थिति
संख्या - सहायक सरणी में गैर-खाली तत्व क्या है (1 ≤ संख्या is गणना)
एम - प्रत्येक तत्व को आवंटित कोशिकाओं की संख्या

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

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

पतित करने का मामला

आवेषण द्वारा अधिकांश छंटाई के लिए, एक रिवर्स-ऑर्डर की गई सरणी सबसे खराब स्थिति है। और एक लाइब्रेरियन, अफसोस, कोई अपवाद नहीं है।

तत्व सहायक सरणी के बाएं किनारे पर होते हैं, जिसके परिणामस्वरूप खाली स्पॉट जल्दी से बाहर निकलते हैं। आपको सरणी को बहुत बार फिर से संतुलित करना होगा।

वैसे, यदि हम लगभग ऑर्डर किए गए सरणी (सरल आवेषण द्वारा छंटाई के लिए सबसे अच्छा मामला) लेते हैं, तो हमें एक ही समस्या मिलती है। नए आगमन वाले तत्व बाईं ओर नहीं चढ़ेंगे, लेकिन सहायक सरणी के दाईं ओर, जो बहुत बार-बार असंतुलित हो जाएगा।

लाइब्रेरी सॉर्ट कुशलता से यादृच्छिक डेटा सेट को संभालता है। आंशिक क्रम (प्रत्यक्ष और रिवर्स दोनों) गति प्रदर्शन को बाधित करता है।

एल्गोरिथ्म जटिलता

यादृच्छिक डेटा के बड़े सेट पर, एल्गोरिथ्म समय जटिलता ओ ( एन लॉग एन ) देता है। बुरा बिलकुल नहीं!

गुणांक selection के सही चयन और द्विआधारी खोज के सफल कार्यान्वयन के साथ यादृच्छिक अद्वितीय (या अधिकतर अद्वितीय) डेटा के सेट पर, असंतुलन की संख्या को कम किया जा सकता है, या यहां तक कि टाला जा सकता है। यह तर्क दिया जा सकता है कि एल्गोरिथ्म में सबसे अच्छा समय जटिलता ओ ( एन ) है।

मूल्य में दोहराए जाने वाले डेटा का एक बड़ा प्रतिशत, साथ ही ऑर्डर किए गए (प्रत्यक्ष या रिवर्स ऑर्डर में) सरणी में उपस्थिति सहायक सरणी के लगातार पुनर्संतुलन की ओर जाता है और, परिणामस्वरूप, सबसे प्रतिकूल मामलों में ओ (एन ² ) के लिए समय जटिलता का क्षरण होता है।

एल्गोरिथ्म के माइनस, ज़ाहिर है, सहायक सरणी को ओ ( एन ) अतिरिक्त मेमोरी की आवश्यकता होती है।

सुधार के संभव तरीके

यद्यपि एल्गोरिथम स्वयं यादृच्छिक डेटा पर शिक्षाप्रद और कुशल है, डेढ़ दशक में, कुछ ने इसमें रुचि दिखाई है।

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

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

और कुछ सुधार करना है:

इष्टतम गुणांक का अनुभवजन्य चयन the।
सम्मिलन बिंदु के सबसे कुशल निर्धारण के लिए द्विआधारी खोज के संशोधन (सामान्य एल्गोरिथ्म की बारीकियों को ध्यान में रखते हुए)।
पुनर्वित्त लागत को कम करना।

यदि आप इन स्थानों को पॉलिश करते हैं, तो हो सकता है कि पुस्तकालय में गति भी समान रूप से समान हो?

स्रोत कोड

मैंने पायथन में कार्यान्वयन को तैयार करने का प्रबंधन नहीं किया, PHP में एक कार्यशील संस्करण है।

मूल एल्गोरिथ्म

function LibrarySort($arr) { global $arr_new;//  $e = 3;//     $rebalance_local = true;// (true)   (false)  //   $newSize = $e * (count($arr) + 1) - 1; $arr_new = array_fill(0, $newSize, null); //       $arr_new[LibrarySort_Pos(1, 1, $newSize)] = $arr[0]; //    -    //     $start = 0; $finish = $newSize - 1; $i = 1; //      while($i < count($arr)) { //        $pos = LibrarySort_BinarySearch($arr[$i], $start, $finish, $newSize); if($pos === false) {//        //    LibrarySort_Rebalance_Total($i, $newSize); } else {//  ,   ,    if($arr_new[$pos] !== null) {//   if($rebalance_local) {//  (+ ) LibrarySort_Rebalance_Local($arr[$i++], $pos, $newSize); } else {//  LibrarySort_Rebalance_Total($i, $newSize); } } else {//   ,   $arr_new[$pos] = $arr[$i++]; } } } //      $pos = 0; for($i = 0; $i <= $newSize - 1; $i++) { if($arr_new[$i] !== null) $arr[$pos++] = $arr_new[$i]; } return $arr; }

पूर्ण पुन: संतुलन के बाद अतिरिक्त सरणी में तत्व की नई स्थिति

 // $number-    $count //     //$number -      ( )  //$count -       //$newSize -     //$number <= $count <= count($arr) <= $newSize) function LibrarySort_Pos($number, $count, $newSize) { return $number * floor(($newSize + 1) / ($count + 1)) - 1; }

सहायक सरणी में सम्मिलन स्थान की द्विआधारी खोज

 //       //$search -     ,      //($start, $finish) -   ,     //$newSize -     function LibrarySort_BinarySearch($search, $start, $finish, $newSize) { global $arr_new;//  //      //      ,     //  ,       while($arr_new[$start] === null && $start < $newSize - 1) { ++$start; } //         , //         if($search == $arr_new[$start]) { return LibrarySort_PosNearby($start, $newSize); //  ,        } elseif($search < $arr_new[$start]) { //      //     if($start > 0) {// $start    $finish = $start; $start = 0; return floor(($start + $finish) / 2); } else {//$start == 0,      return $start;//    ,    } } //      ,     //  ,       while($arr_new[$finish] === null && $finish > 0) { --$finish; } //         , //         if($search == $arr_new[$finish]) { return LibrarySort_PosNearby($finish, $newSize); //  ,        } elseif($search > $arr_new[$finish]) { //      //     if($finish < $newSize - 1) {// $finish    $start = $finish; $finish = $newSize - 1; return ceil(($start + $finish) / 2); } else {//$finish == $newSize - 1,      return $finish;//    ,    } } //     , //,    -   //   ,       If($finish - $start > 1) {//   ,    3  $middle = ceil(($start + $finish) / 2); //   $middle_Pos = 0; // ""     $offset = 0; //         //,    /,      while($middle - $offset > $start && $middle_Pos == 0){ if($arr_new[$middle - $offset] !== null) { $middle_Pos = $middle - $offset; } elseif($middle + $offset < $finish && $arr_new[$middle + $offset] !== null) { $middle_Pos = $middle + $offset; } ++$offset; } //    , ,     , //              If($middle_Pos) { if($arr_new[$middle_Pos] == $search) { return LibrarySort_PosNearby($middle_Pos, $newSize); } else { if($arr_new[$middle_Pos] > $search) { $finish = $middle_Pos; } else {//$arr_new[$middle_Pos] < $search $start = $middle_Pos; } return LibrarySort_BinarySearch($search, $start, $finish, $newSize); } } else {//$middle_Pos == 0 -   (   )     return $middle;//   - ,     } } else {//  ,       return floor(($start + $finish) / 2); } return false;//  ,       }

यदि खोज के दौरान तत्व खंड के सिरों में से एक के बराबर है

 //    ,        //$start - ,        //$newSize -     function LibrarySort_PosNearby($start, $newSize) { global $arr_new;//  //       for($left = $start - 1; $left >= 0; $left--) { if($arr_new[$left] === null) {//  return $left;//   } elseif($arr_new[$left] <> $arr_new[$start]) {//     break; //   ,      } } //     ,    for($right = $start + 1; $right <= $newSize - 1; $right++) { if($arr_new[$right] === null) {//  return $right; //   } elseif($arr_new[$right] <> $arr_new[$start]) {//     break; //   ,      } } return $start; //          .      ,     }

अतिरिक्त सरणी का स्थानीय पुनर्संतुलन

 //    //$insert - ,    //$pos -            //$newSize -     function LibrarySort_Rebalance_Local($insert, $pos, $newSize) { global $arr_new;//  // $pos  $insert,       while($pos - 1 >= 0 && $arr_new[$pos - 1] !== null && $arr_new[$pos - 1] > $insert) {--$pos;} while($pos + 1 <= $newSize - 1 && $arr_new[$pos + 1] !== null && $arr_new[$pos + 1] < $insert) {++$pos;} $middle = (integer) $newSize / 2;//  if($pos <= $middle) {//      if($arr_new[$pos] !== null && $arr_new[$pos] < $insert) ++$pos; //  $right = $pos; while($arr_new[++$right] !== null) {} for($i = $right; $i > $pos; $i--) { $arr_new[$i] = $arr_new[$i - 1]; } } else {//      if($arr_new[$pos] !== null && $insert < $arr_new[$pos]) --$pos; //  $left = $pos; while($arr_new[--$left] !== null) {} for($i = $left; $i < $pos; $i++) { $arr_new[$i] = $arr_new[$i + 1]; } } $arr_new[$pos] = $insert; }

अतिरिक्त सरणी का पूर्ण पुनर्संतुलन

 //    //$count -        //$newSize -     function LibrarySort_Rebalance_Total($count, $newSize) { global $arr_new;//  global $library_Number;//     global $library_LeftPos;//        $library_Number = $count; //        $library_LeftPos = $newSize - 1;// ,     //         $i = $newSize - 1; while($i >= 0) { if($arr_new[$i] !== null) {//   $pos = LibrarySort_Pos($library_Number, $count, $newSize);//   newSize=$newSize"); if($i == $pos) {//      --$i;//      } elseif($i < $pos) {//    $arr_new[$pos] = $arr_new[$i]; $arr_new[$i] = null; --$i;//      } else {//$i > $pos -     //      LibrarySort_RemoveLeft($i, $pos, $count, $newSize); $i = ($i > $library_LeftPos) ? $library_LeftPos - 1 : --$i; } --$library_Number;//      } else {// ,   --$i;//      } } }

पूर्ण रीबैलेंसिंग के साथ तत्व को बाईं ओर ले जाना

 //     . //    ,   //$i -     ,    //$pos -       //$count -        //$newSize -     function LibrarySort_RemoveLeft($i, $pos, $count, $newSize) { global $arr_new;//  global $library_Number;//     global $library_LeftPos;//        $left = false; $left_Pos = false;//      $j = $i;//      //     while($j > 0 && $left === false) {//            --$j; //     if($arr_new[$j] !== null) $left = $j;//    } if($left === false || $left < $pos) {//   (  )    //     } else { //$left >= $pos,     --$library_Number;//,       $left_Pos = LibrarySort_Pos($library_Number, $count, $newSize);//     //        LibrarySort_RemoveLeft($left, $left_Pos, $count, $newSize); //  ,     } //    ,   $arr_new[$pos] = $arr_new[$i]; $arr_new[$i] = null; //,         if($pos < $library_LeftPos) $library_LeftPos = $pos; }

मुझे विधि के सामान्य विवरण के आधार पर खुद को खरोंच से कोड करना पड़ा। मैंने त्वरित छँटाई के करीब एक गति नहीं देखी, मेरे पुस्तकालय प्रकार विकल्प में त्वरित छँटाई की तुलना में 10-20 गुना धीमी है। लेकिन निश्चित रूप से, इसका कारण यह है कि मेरा कार्यान्वयन बहुत अधिक कच्चा है, बहुत कुछ ध्यान में नहीं लिया गया है।

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

युपीडी। मार्टिन फराह-कोल्टन ने मुझे उत्तर दिया कि उन्होंने कभी कार्यान्वयन नहीं किया:

मुझे डर है कि हमने उस एल्गोरिदम को कभी लागू नहीं किया।

मुख्य बात आइडिया है :)

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

नाम	लाइब्रेरी सॉर्ट, लाइब्रेरी सॉर्ट
अन्य नाम	डाला प्रविष्टि प्रकार
लेखक	माइकल ए। बेंडर, मार्टीन फरच-कोल्टन, मिगुएल मोस्टेइरो
साल	2004
वर्ग	निवेशन शॉर्ट्स
तुलना	वहाँ है
समय की जटिलता	सबसे अच्छा	ओ ( एन )
	मध्यम	ओ ( एन लॉग एन )
	सबसे खराब	ओ ( एन ² )
अतिरिक्त स्मृति जटिलता	ओ ( एन )

संदर्भ

लाइब्रेरी सॉर्ट

लाइब्रेरी सॉर्ट एल्गोरिथ्म विज़ुअलाइज़ेशन

प्रविष्टि प्रकार O (n लॉग एन) है

एल्गोरिथ्म के लेखक:

माइकल ए बेंडर
मार्टिन फराह-कोल्टन
मिगुएल मोस्टिरो

श्रृंखला लेख:

एक्सेल आवेदन AlgoLab.xlsm
एक्सचेंज सॉर्ट
निवेशन शॉर्ट्स
- लाइब्रेरियन क्रमबद्ध
- सॉलिटेयर सॉर्ट
- सॉर्ट "हनोई का टॉवर"
- युवा टेबल छँटाई
- इनवर्ट सॉर्ट करें
- क्रमबद्ध तुलना डालें
चयन के आधार पर छाँटें
मर्ज करना
वितरण के आधार पर छाँटें
हाइब्रिड सॉर्टिंग

AlgoLab में सॉर्ट किया गया। तो आप छोटे डेटा सेट के साथ प्रयोग कर सकते हैं।

इस मामले में, आप यह तय कर सकते हैं कि सहायक सरणी मुख्य से कितनी बार बड़ी है। गुणांक fficient का चयन करने के लिए , आप "लाइब्रेरी सॉर्टिंग" के साथ सेल पर राइट-क्लिक कर सकते हैं और "नोट बदलें" का चयन कर सकते हैं। और नोट में, ध्यान से 2 से 5 के लिए पूर्णांक मान सेट करें। यदि आप इन संख्याओं के बजाय कुछ और दर्ज करते हैं, तो डिफ़ॉल्ट मान = 2 का उपयोग किया जाएगा।

आप रीबैलेंसिंग के प्रकार का चयन भी कर सकते हैं। यदि आप स्थानीय = 1 सेट करते हैं, तो स्थानीय रीबैलेंसिंग का उपयोग किया जाएगा। यदि स्थानीय = 0 - पूर्ण।

और विज़ुअलाइज़ेशन शुरू करने से पहले प्रक्रिया शीट के लिए इष्टतम पैमाने निर्धारित करना न भूलें, अन्यथा सहायक सरणी स्क्रीन पर फिट नहीं होगी।