🧜🏿 👒 👩🏽‍💼 चिकनी छँटाई 🌞 📴 🛌🏿

हम कई तरह के ढेरों में डूबे रहते हैं।

आज हम एक सुरुचिपूर्ण आदेश पद्धति का विश्लेषण करेंगे जो लियोनार्डो की संख्या के आधार पर विशेष ढेर का उपयोग करती है।

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

EDISON.

, Android iOS.

! ;-)

हीप छँटाई अपने आप में बहुत अच्छी है, क्योंकि इसकी समय जटिलता डेटा की परवाह किए बिना ओ ( एन लॉग एन ) है । एक सरणी का प्रतिनिधित्व नहीं करने के लिए, हेप्सोर्ट की जटिलता कभी भी ओ ( एन ² ) को नीचा नहीं करती है , जो कि हो सकता है, उदाहरण के लिए, त्वरित छंटाई के साथ। सिक्के का दूसरा पहलू यह है कि एक बाइनरी हीप द्वारा छंटाई को तेज नहीं किया जा सकता है, O ( n ) जटिलता की भी उम्मीद नहीं की जा सकती है (लेकिन कुछ शर्तों के तहत एक ही त्वरित छंटाई, ऐसे संकेतकों तक पहुंच सकती है)।

सामान्य तौर पर, एजेंडे पर एक सवाल था: क्या यह संभव है कि एक समय पर ढेर, एक तरफ से छंटनी की जटिलता कम न हो।O ( n लॉग एन ) , लेकिन एक अनुकूल परिदृश्य में (विशेष रूप से, यदि एक लगभग सॉर्ट किया गया सरणी संसाधित किया जाता है) O ( n ) में वृद्धि हुई है ?

इस मुद्दे को व्यक्तिगत रूप से खुद एग्जर्स डीजकस्ट्रा ने संबोधित किया, जिन्होंने पाया कि हां, यह संभव है।

यह माना जाता है कि जो लोग इस लेख को पढ़ते हैं वे समझते हैं कि कैसे ढेर सामान्य रूप से काम करता है, वे जानते हैं कि छंटाई का पेड़ क्या है और एक स्थानांतरण की आवश्यकता क्यों है। यदि किसी को इस ज्ञान में अंतराल है, तो पढ़ना जारी रखने से पहले, मेरा सुझाव है कि आप पिछले लेख को पढ़ें ।

क्या एक बाइनरी हीप के साथ गलत है

आइए एक नज़र डालें कि कैसे हाईपोसर्ट लगभग ऑर्डर किए गए सरणी को सॉर्ट करता है और देखें कि यह एल्गोरिथम ऐसे इनकमिंग डेटा को तेजी से प्रोसेस क्यों नहीं करता है।

"एन-पिरामिड द्वारा क्रमबद्ध करें" लेख पर जाने के लिए एनीमेशन पर क्लिक करें।

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

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

लियोनार्डो संख्या

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

लियोनार्डो संख्या लगभग फाइबोनैचि संख्याओं की तरह है, लेकिन केवल बेहतर है।
लियोनार्दो की संख्याओं की एक श्रृंखला पुनरावर्ती दी गई है:

एल ₀ = 1
एल ₁ = 1
एल _एन = एल _{एन - 1} + एल _{एन - 2} + 1

पहले 20 लियोनार्डो संख्या:
1, 1, 3, 5, 9, 15, 25, 41, 67 , 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529

बिल्कुल किसी भी पूर्णांक को लियोनार्दो संख्याओं के योग के रूप में दर्शाया जा सकता है, जिसमें विभिन्न सीरियल नंबर होते हैं।

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

यहाँ 21 तत्व की एक सरणी का एक उदाहरण है, जिसमें तीन लियोनार्ड ढेर शामिल हैं। प्रत्येक ढेर में, नोड्स की संख्या लियोनार्डो की किसी भी संख्या से मेल खाती है।

जानने के लिए महत्वपूर्ण बिंदु:

प्रत्येक लियोनार्डोव ढेर एक असंतुलित बाइनरी ट्री है।
प्रत्येक ढेर की जड़ संगत उपर्रे का अंतिम (और नियमित रूप से बाइनरी हीप के रूप में) पहला नहीं है।
अपने सभी वंशजों के साथ कोई भी नोड एक छोटे क्रम का लियोनार्ड ढेर है।

निर्माण और विघटित ढेर

लियोनार्डो संख्या के लिए पुनरावृत्ति सूत्र में,

L _n = L _{n - 1} + L _{n - 2} + 1

इकाई पर बहुत प्रसन्न होता है।

और यही कारण है। मान लें कि हमारे पास सरणी में दो आसन्न उपजातियाँ हैं जो दो आसन्न लियोनार्डो नंबरों पर निर्मित ढेर के अनुरूप हैं। इन उपप्रकारों के तुरंत बाद तत्व का उपयोग करते हुए, इन उपग्रहों को एक सामान्य ढेर में जोड़ा जा सकता है, जो अगले लियोनार्ड संख्या से मेल खाती है।

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

एल्गोरिथ्म के दूसरे चरण में, रिवर्स प्रक्रिया होती है - हम ढेर को पार्स करते हैं। यदि हम जड़ को ढेर में हटा देते हैं, तो हमें दो पिछले लियोनार्दो संख्याओं के समान दो छोटे ढेर मिलते हैं। यह किया जा सकता है क्योंकि:

एल _एन - 1 = एल _{एन - 1}+ L _{n - 2}

फाइबोनैचि संख्या में ऐसी कोई उपयोगी इकाई नहीं है, इसलिए हम फाइबोनैचि हीप का उपयोग नहीं करते हैं।

चिकना सॉर्ट :: चिकना

अंतिम एल्गोरिथ्म:

I. सरणी से लियोनार्ड ढेर का एक गुच्छा बनाएं, जिनमें से प्रत्येक एक छंटाई का पेड़ है।
- I.1। सरणी के तत्वों को बाईं से दाईं ओर स्थित करें।
- II.1। हम जाँचते हैं कि क्या वर्तमान तत्व का उपयोग करके लियोनार्ड ढेर के मौजूदा ढेर में दो सबसे बाएं ढेर को जोड़ना संभव है:
  - II.1.a. यदि हाँ, तो हम दो सबसे बाएं ढेर को एक में जोड़ते हैं, वर्तमान तत्व इस ढेर का मूल बन जाता है, हम संयुक्त ढेर के लिए एक दरार बनाते हैं।
  - II.1.b. यदि नहीं, तो लियोनार्ड ढेर के मौजूदा ढेर में एक नया ढेर (अब तक एक नोड से मिलकर) के रूप में वर्तमान तत्व जोड़ें।
II. , :
- II.1. . , .
- II.2. ( ) ( ).
- II.3. , . .
- II.4. ( ), .
- II.5। अधिकतम तत्व को अंत तक ले जाने के बाद, सरणी का सॉर्ट किया गया हिस्सा बढ़ गया, और अनसर्टेड भाग कम हो गया। सरणी के शेष भाग के लिए चरण II.1-II.4 को दोहराएं।

पायथन कार्यान्वयन उदाहरण

import random

def smoothsort(lst):

    #    
    leo_nums = leonardo_numbers(len(lst))


    #       
    heap = []

    #   
    #       
    #       
    for i in range(len(lst)):
        if len(heap) >= 2 and heap[-2] == heap[-1] + 1:
            heap.pop()
            heap[-1] += 1
        else:
            if len(heap) >= 1 and heap[-1] == 1:
                heap.append(0)
            else:
                heap.append(1)
        restore_heap(lst, i, heap, leo_nums)

    #  
    for i in reversed(range(len(lst))):
        if heap[-1] < 2:
            heap.pop()
        else:
            k = heap.pop()
            t_r, k_r, t_l, k_l = get_child_trees(i, k, leo_nums)
            heap.append(k_l)
            restore_heap(lst, t_l, heap, leo_nums)
            heap.append(k_r)
            restore_heap(lst, t_r, heap, leo_nums)

#   ,     
def leonardo_numbers(hi):

    a, b = 1, 1
    numbers = []
    while a <= hi:
        numbers.append(a)
        a, b = b, a + b + 1
    return numbers

#        
def restore_heap(lst, i, heap, leo_nums):
    
    #      
    
    current = len(heap) - 1
    k = heap[current]

    while current > 0:
        j = i - leo_nums[k]
        if (lst[j] > lst[i] and
            (k < 2 or lst[j] > lst[i-1] and lst[j] > lst[i-2])):
            lst[i], lst[j] = lst[j], lst[i]
            i = j
            current -= 1
            k = heap[current]
        else:
            break

    # 
    
    while k >= 2:
        t_r, k_r, t_l, k_l = get_child_trees(i, k, leo_nums)
        if lst[i] < lst[t_r] or lst[i] < lst[t_l]:
            if lst[t_r] > lst[t_l]:
                lst[i], lst[t_r] = lst[t_r], lst[i]
                i, k = t_r, k_r
            else:
                lst[i], lst[t_l] = lst[t_l], lst[i]
                i, k = t_l, k_l
        else:
            break

#         ,
#     
def get_child_trees(i, k, leo_nums):

    t_r, k_r = i - 1, k - 2
    t_l, k_l = t_r - leo_nums[k_r], k - 1
    return t_r, k_r, t_l, k_l

#  
def main(n):
    lst = list(range(n))
    random.shuffle(lst)
    print(lst)
    smoothsort(lst)
    print(lst)

समय की जटिलता

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

बचत केवल स्थानांतरण के कारण होती है। लगभग ऑर्डर किए गए डेटा में, पेड़ को दूसरे चरण में धीरे-धीरे विघटित करने के बाद सहित, उथले उथले पेड़ में। प्रारंभ में यादृच्छिक डेटा में, स्थानांतरण अधिक महंगा है, क्योंकि यह अक्सर अपने ढेर में अंतिम स्तर तक गिरता है।

चलो कुल समय जटिलता का अनुमान लगाते हैं।

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

इसलिए, पहले चरण में, सबसे अच्छा समय जटिलता है:
लगभग ऑर्डर किए गए डेटा के लिए - O ( n ),
यादृच्छिक डेटा के लिए - O ( n log n )।

दूसरे चरण के लिए, स्थिति समान है। अगले अधिकतम का आदान-प्रदान करते समय, आपको फिर से उस रूट पर ढेर को दबाने की जरूरत है, जो यह था। और ऑर्डर किए गए और अव्यवस्थित डेटा के लिए स्थानांतरण मीट्रिक अलग-अलग होंगे।

दूसरे चरण में, सबसे अच्छा समय जटिलता पहले के समान है:
लगभग ऑर्डर किए गए डेटा के लिए - हे ( एन ),
यादृच्छिक डेटा के लिए - ओ ( एन लॉग एन )।

पहले और दूसरे चरणों के लिए समय जटिलता जोड़ना:
लगभग ऑर्डर किए गए डेटा के लिए - O (2 n ) = O ( n ),
यादृच्छिक डेटा के लिए - O (2 n log n ) = O ( n log n )।

सामान्य तौर पर, सहज छांटने के लिए सबसे खराब और औसत समय जटिलता हे ( एन लॉग एन ) है।
अपनी गणना में डीजकस्ट्रा (जो मैं आपको बोर नहीं करेगा) ने साबित किया कि आने वाली डेटा की तुलना में सबसे अधिक जटिलता सुगमता से ओ ( एन ) तक जाती है। इसलिए नाम - चिकनी छँटाई।

अतिरिक्त स्मृति जटिलता

डेटा को लियोनार्ड ढेर के एक समूह में विघटित करने के लिए, आपको बस यह याद रखने की आवश्यकता है कि लियोनार्डो नंबर प्रत्येक चरण में शामिल हैं। इन नंबरों को जानने के बाद, ढेर खुद को एल्गोरिदम से जोड़ दिया जाता है। यह संख्या श्रृंखला बहुत तेज़ी से बढ़ती है, इसलिए बड़े सरणियों के लिए भी आपको लियोनार्ड संख्याओं के एक बहुत छोटे सेट की आवश्यकता होगी।

द्विपद हीप प्रकार :: द्विपद हीप प्रकार

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

सिद्धांत रूप में, आप द्विपद के आधार पर एक चिकनी छँटाई कर सकते हैं:

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

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

अगली सीरीज का ट्रेलर

हालांकि, यहां तक कि अगर एक द्विपद ढेर चिकनी छँटाई के लिए सबसे अच्छा विकल्प नहीं है, तो आपको इसे पूरी तरह से त्याग नहीं करना चाहिए।

यदि द्विपद वृक्ष थोड़ा संशोधित है और इसके चारों ओर जाने के लिए पूरी तरह से अलग (बहुत बोल्ड) विचारों का उपयोग किया जाता है, तो हमें एक मूल और प्रभावी एल्गोरिथ्म मिलता है जिसके अपने फायदे हैं। अगली बार हम किस बारे में बात करने जा रहे हैं?

हीप द्वारा अगली छँटाई के साथ लेख पर जाने के लिए एनीमेशन पर क्लिक करें।

संदर्भ

चिकना / चिकना

लियोनार्डो संख्या , द्विपद ढेर / द्विपद ढेर

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

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

AlgoLab ऐप में आज की सहज छँटाई को जोड़ा गया है। साथ ही एक बोनस - और एक द्विपद ढेर के साथ छंटनी। तो जो ढेर ढेर पर डेटा को व्यक्तिगत रूप से चलाना चाहता है - मैक्रो के साथ एक्सेल-फ़ाइल को अपडेट करें।

चिकनी छँटाई