الفرز السلس

EDISON.

, Android iOS.

! ;-)

ما هو الخطأ في كومة الذاكرة المؤقتة الثنائية

أرقام ليوناردو

1. كل كومة ليوناردوف هي شجرة ثنائية غير متوازنة.
2. جذر كل كومة هو العنصر الأخير (وليس الأول ، كما في كومة الذاكرة المؤقتة العادية) من المصفوفة الفرعية المقابلة.
3. أي عقدة مع جميع أحفادها هي أيضًا كومة ليونارد ذات ترتيب أصغر.

بناء وتفكيك أكوام

الفرز السلس :: الفرز السلس

• 1. نقوم بإنشاء مجموعة من أكوام Leonard من المصفوفة ، كل منها عبارة عن شجرة فرز.
  • I.1. كرر فوق عناصر المصفوفة من اليسار إلى اليمين.
  • II.1. تحقق مما إذا كان العنصر الحالي يمكن أن يجمع بين كومة الذاكرة المؤقتة الموجودة في أقصى اليسار في كومة الذاكرة المؤقتة الموجودة في كومة Leonard:
    • II.1.a. إذا كانت الإجابة بنعم ، فإننا نجمع الكمينين في أقصى اليسار في عنصر واحد ، ويصبح العنصر الحالي هو جذر هذا الكومة ، ونقوم بعمل شبكة للكومة المجمعة.
    • II.1.b. إذا لم يكن الأمر كذلك ، فأضف العنصر الحالي ككومة جديدة (تتكون حتى الآن من عقدة واحدة) إلى كومة الذاكرة المؤقتة الموجودة في Leonard.
• II. , :
  • II.1. . , .
  • II.2. ( ) ( ).
  • II.3. , . .
  • II.4. ( ), .
  • II.5. بعد تحريك العنصر الأقصى إلى النهاية ، زاد الجزء المصنف من الصفيف ، وانخفض الجزء غير المصنف. كرر الخطوات من II.1-II.4 للجزء المتبقي غير المصنف من الصفيف.

مثال على تطبيق Python

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)

تعقيد الوقت

تعقيد الذاكرة الزائدة

فرز كومة ذات الحدين :: فرز كومة ذي الحدين

مقطورة السلسلة التالية

المراجع

مقالات سلسلة:

• تطبيق Excel AlgoLab.xlsm
• أنواع التبادل
• أنواع الإدراج
• فرز حسب التحديد
  • أنواع الكومة: N-Pyramids
  • أنواع الكومة: أرقام ليوناردو
  • نوع الكومة: كومة ضعيفة
  • أنواع الحفريات: شجرة ديكارتية
  • فرز كومة أخرى: كومة مرآة ، كومة صغيرة ، غربلة من أسفل إلى أعلى
  • أنواع الكومة: Jung Heap
• دمج الأنواع
• فرز حسب التوزيع
• الفرز الهجين