فرز البطولة

نستمر في التعرف على أكوام مختلفة وفرز الخوارزميات باستخدام هذه الأكوام. اليوم لدينا ما يسمى شجرة البطولة.

EDISON .




, . , .



computer science ;-)

تتمثل الفكرة الرئيسية لفرز البطولة في استخدام كومة مساعدة صغيرة نسبيًا (مقارنة بالصفيف الرئيسي) ، والتي تعمل كقائمة انتظار ذات أولوية. في هذا الكومة ، تتم مقارنة العناصر الموجودة في المستويات الدنيا ، ونتيجة لذلك ترتفع العناصر الأصغر (في هذه الحالة ، الشجرة التي لدينا MIN-HEAP) ، والحد الأدنى الحالي من جزء عناصر الصفيف الذي وقع في هذا الكومة يطفو إلى الجذر. يتم نقل الحد الأدنى إلى مصفوفة إضافية من "الفائزين" ، ونتيجة لذلك تتم مقارنة / نقل العناصر المتبقية في كومة الذاكرة المؤقتة - والآن يوجد حد أدنى جديد في جذر الشجرة. لاحظ أنه مع مثل هذا النظام ، يكون الحد الأدنى التالي أكبر في القيمة من النظام السابق - ثم يتم تجميع مجموعة مرتبة جديدة من "الفائزين" بسهولة ، حيث تتم إضافة الحد الأدنى الجديد ببساطة إلى نهاية المصفوفة الإضافية.



يؤدي نقل الحد الأدنى إلى مصفوفة إضافية إلى حقيقة أن الوظائف الشاغرة تظهر في كومة الذاكرة المؤقتة للعناصر التالية من الصفيف الرئيسي - ونتيجة لذلك تتم معالجة جميع العناصر بترتيب قائمة الانتظار.



الدقيقة الرئيسية هي أنه بالإضافة إلى "الفائزين" هناك أيضًا "خاسرون". إذا كانت بعض العناصر قد تم نقلها بالفعل إلى مصفوفة "الفائزين" ، فإن كانت العناصر غير المجهزة أصغر من هؤلاء "الفائزين" ، فلا فائدة من فرزها عبر شجرة البطولة في هذه المرحلة - سيكون إدراج هذه العناصر في مصفوفة "الفائزين" مكلفًا للغاية (في لا يمكنك إنهاءها ، ولكن لوضعها في البداية ، يجب عليك تغيير الحدود الدنيا المدرجة مسبقًا). يتم إرسال هذه العناصر التي لم تنجح في احتواء مصفوفة "الفائزين" إلى مصفوفة "الخاسرين" - وسوف تمر عبر شجرة البطولة في أحد التكرارات التالية ، عندما تتكرر جميع الإجراءات للخاسرين المتبقين.



ليس من السهل العثور على تطبيق لهذه الخوارزمية على الإنترنت ، ولكن تم العثور على تطبيق واضح ولطيف في Ruby على YouTube. كود جافا مذكور أيضًا في قسم "الروابط" ، لكنه لا يبدو مقروءًا هناك.

  #         
  require_relative "pqueue"
	
  #     
  MAX_SIZE = 16

  def tournament_sort(array)
    #   ,   ""
    return optimal_tourney_sort(array) if array.size <= MAX_SIZE
    bracketize(array) #   ,   ""
  end
	
  #     
  def bracketize(array)
	
    size = array.size
    pq = PriorityQueue.new
    #    
    pq.add(array.shift) until pq.size == MAX_SIZE
    winners = [] #  ""
    losers = [] #  ""
		
    #      
    until array.empty?
			
      #  ""  ?
      if winners.empty?
        #      ""
        winners << pq.peek
        #     
        pq.remove 
      end
			
      #      ,   ""
      if array.first > winners.last
        pq.add(array.shift) #       
      else #        ""
        losers << array.shift #     ""
      end
			
      #     ,     ""
      winners << pk.peek unless pk.peek.nil?
      pq.remove #     
			
    end
		
    #   ,      - ?
    until pq.heap.empty?
      winners << pq.peek #     ""
      pq.remove #     
    end

    #   ""  , , ,
    #  "" -   
    return winners if losers.empty?
		
    #    ,    ""
    #   ""
    array = losers + winners
    array.pop while array.size > size
    bracketize(array) #   
		
  end
	
  #       
  def optimal_tourney_sort(array)
    sorted_array = [] #    
    pq = PriorityQueue.new
    array.each { |num| pq.add(num) } #     -
    until pq.heap.empty? #  -  
      sorted_array << pq.heap[0] 
      pq.remove #     
    end
    sorted_array #  
  end
	
  # 
  if $PROGRAM_NAME == __FILE__
    #  
    shuffled_array = Array.new(30) { rand(-100 ... 100) }
    #   
    puts "Random Array: #{shuffled_array}"
    #   
    puts "Sorted Array: #{tournament_sort(shuffled_array)}"
  end

يعد هذا تنفيذًا ساذجًا ، حيث يتم دمج هذه المصفوفات بعد كل تقسيم إلى "الخاسرين" و "الفائزين" ، ثم يتم تكرار جميع الإجراءات مرة أخرى للمجموعة المدمجة. إذا كانت هناك عناصر "خاسرة" في المصفوفة المدمجة أولاً ، فإن غربلة كومة البطولة ستطلبها مع "الفائزين".





هذا التطبيق بسيط جدًا وواضح ، لكنك لن تذكره بفاعلية. يمر "الفائزون" المصنفين في شجرة البطولة عدة مرات ، وهو أمر غير ضروري بشكل واضح. أفترض أن تعقيد الوقت هنا هو log-quadratic ، O ( n log ² n ) .

خيار دمج المسارات المتعددة

يتم تسريع الخوارزمية بشكل ملحوظ إذا لم يتم تمرير العناصر المرتبة التي مرت عبر الغربال عبر سباقات البطولة مرة أخرى.



بعد تقسيم الصفيف غير المنظم إلى "فائزين" مصنفين و "فاشلين" غير مرتبين ، يتم تكرار العملية برمتها من جديد فقط "فاشلين". في كل تكرار جديد ، ستتراكم مجموعة من المصفوفات مع "الفائزين" وستستمر بهذه الطريقة حتى لا يكون هناك "خاسرون" في أي خطوة. بعد ذلك ، كل ما تبقى هو دمج جميع صفائف "الفائزين". نظرًا لأن جميع هذه الصفائف مرتبة ، فإن هذا الدمج يستمر بأقل جهد.





في هذا النموذج ، قد تجد الخوارزمية تطبيقًا مفيدًا بالفعل. على سبيل المثال ، إذا كان عليك العمل مع البيانات الضخمة ، فسيتم إصدار حزم البيانات المرتبة التي يمكنك فعلها بالفعل أثناء معالجة كل شيء آخر.



كل من ن عناصر من مجموعة يذهب من خلال شجرة البطولة مرة واحدة فقط، والتي تأخذ O (سجل ن ) وقت. في مثل هذا التطبيق ، يكون للخوارزمية التعقيد الزمني الأسوأ / المتوسط O ( n log n ) .

في ختام الموسم

تم الانتهاء من السلسلة على أنواع كومة الذاكرة المؤقتة. يبقى أن نقول عن أكثرها فاعلية.

المراجع

Tournament sort



Priority queue



Tournament sort in Java



The Theory Behind the The Theory Behind the z/Architecture Sort Assist Instructions



Using Tournament Trees to Sort



Tournament Sort Demo Ruby



Tournament Sort Visualization



Tournament Sort Data Structure UGC NET DS



Tournament Sort Algorithm — a Heapsort variant

:

• Excel- AlgoLab.xlsm
• • : n-
  • :
  • :
  • :
  • :
  • :

تمت إضافة تصنيف اليوم إلى تطبيق AlgoLab الذي يستخدمه - قم بتحديث ملف excel باستخدام وحدات الماكرو.



في التعليقات على الخلية باسم الفرز ، يمكنك تحديد بعض الإعدادات. الطريقة

المتغيرة هي شجرة بطولة متعددة الاتجاهات (فقط في حالة ، من الممكن جعل هذه الشجرة ليست ثنائية فقط ، ولكن أيضًا ثلاثية ، رباعية ، ومستقرة).

متغير قائمة الانتظار هو حجم قائمة الانتظار الأصلية (عدد العقد في أدنى مستوى من الشجرة). نظرًا لأن الأشجار ممتلئة ، على سبيل المثال ، بالطريقة = 2 ، حددت قائمة الانتظار = 5 ، فسيتم زيادة حجم قائمة الانتظار إلى أقرب قوة من اثنتين (في هذه الحالة ، حتى 8).

متغير NWayMerge يأخذ القيمة 1 أو 0 - يشير إلى ما إذا كان سيتم استخدام دمج متعدد المسارات أم لا.