Geekly articles weekly

ترتيب العلم الأمريكي


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

نحن منخرطون في ترقية البرامج وترحيلها ، وكذلك تطوير تطبيقات الهاتف المحمول Android و iOS .

نحن نحب نظرية الخوارزميات! ؛-)

علم اللونين



أولاً ، ضع في اعتبارك الحالة عند توزيع الأرقام في الصفيف المفروزة في جزئين فقط. للبساطة ، نفترض أن لدينا مجموعة من الأصفار (ترتيب منخفض) والأخرى (ترتيب عالي).

وبالتالي ، لدينا فقط "نطاقان": في أحدهما سنحرك البتات الأقل دلالة (الأصفار) ، وفي الجانب الآخر البتات الأعلى (الوحدات). سوف أي علم اللونين يذهب للتظاهر. على سبيل المثال ، علم أوكرانيا.



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

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

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

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

مشكلة العلم الوطني الهولندي :: مشكلة العلم الوطني الهولندي



نحن نعقد المهمة قليلاً ، لا تنظر في رقمين ، ولكن ثلاثة. دعنا نمتلك عناصر المصفوفة تنتمي إلى أدنى (أصفار) ووسط (وحدات) وأقدم (رقمان).

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



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

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

ترتيب العلم الأمريكي :: ترتيب العلم الأمريكي



الآن ، في تفسيراتنا ، يمكننا الانتقال إلى العلم الأمريكي متعدد النطاقات.

عندما لا يكون لدينا رقمان ، وليس ثلاثة ، ولكن أي عدد من الأرقام ، فإننا نصلح حيث يجب أن يبدأ كل رقم ("الفرقة") ونعيد رسم العناصر الموجودة في "نطاقاتها".

في هذه الخوارزمية ، لا يتم اعتبار الأرقام عادةً كعدد عشري ، ولكن في عمق بت مختلف ، غالبًا ما تكون قوة اثنين. في كثير من الأحيان ، يتم اعتبار الرقم 256 كأساس لعمق البت (أقل كثيرًا إلى حد ما من 128) ، مما يتيح لك تكييف الفرز بكفاءة لترتيب الأوتار. بالنسبة للأرقام الخاصة بعمق البتات ، من الملائم أن تأخذ صغيرة 2 ن (2 ، 4 ، 16 ، إلخ) ، والتي تسمح لك بالمقارنة عن طريق التبديل بالبت ، بدلاً من الرفع إلى قوة عند مقارنة الأرقام العشرية.

تُظهر الرسوم المتحركة مثالًا على عمق البت مع القاعدة 16:



  1. عند المرور الأول - ابحث عن الحد الأقصى من أجل تحديد الحد الأقصى لعدد البتات بين العناصر في الصفيف (من أجل استخراج البتات المحددة بشكل صحيح من الحساب من العناصر).
  2. ثم يحدث معالجة العودية. عند الاتصال ، تتم الإشارة إلى حدود المصفوفة الفرعية والبت المعالَج الحالي. في المكالمة الأولى ، الصفيف بأكمله عبارة عن صفيف فرعي ؛ يتم أخذ البتة الأولى على اليسار.
  3. من بين عناصر الطبقة الفرعية ، يتم إجراء حساب أولي - عدد مرات حدوث كل رقم في الفئة الحالية. يتيح لك هذا العدد تحديد توطين هذه الأرقام من الأرقام (أي ، حدود وموقع "النطاق" الذي تريد نقل العناصر التي تحتوي على الرقم التالي في رقم معين معروفة). في الواقع ، فإن التعريب هو مؤشرات إلى "نطاقات" حيث يجب نقل العناصر المقابلة.
  4. وفقًا لمؤشرات التعريب ، تتم عملية التبادل على الفور - الرقم الموجود في الفئة يوضح المكان الذي يجب إرسال العنصر إليه ، ويحل مكان عنصر آخر حدث فيه التبادل. يتم تنفيذ هذا الشرط حتى ، في التبادل التالي ، لا يوجد عنصر قادم من مكان آخر في مكانه (ثم يمكنك الانتقال إلى العنصر التالي من الصفيف الفرعي وبالمثل تنفيذ هذا البند له).
  5. بعد ، نتيجة لعمليات التبادل ، أعيد توزيع العناصر في كتل بالأرقام في الرقم التالي ، يحدث تكرار - يتم تطبيق نفس الخوارزمية على كل كتلة كخلفية فرعية ، ويتم أخذ المجموعة التالية كرقم حالي.

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

ترتيب العلم الأمريكي - تنفيذ بايثون
#           def get_radix_val(x, digit, radix) -> int: return int(floor(x / radix**digit)) % radix #             def compute_offsets(a_list, start: int, end: int, digit, radix) -> list: #          counts = [0 for _ in range(radix)] for i in range(start, end): #        #         val = get_radix_val(a_list[i], digit, radix) counts[val] += 1 #       #          offsets = [0 for _ in range(radix)] sum = 0 #         for i in range(radix): offsets[i] = sum sum += counts[i] return offsets #      def swap(a_list, offsets, start: int, end: int, digit, radix) -> None: i = start #          next_free = copy(offsets) #        #   (       ) cur_block = 0 while cur_block < radix-1: # if i >= start + offsets[cur_block+1]: cur_block += 1 continue radix_val = get_radix_val(a_list[i], digit, radix) if radix_val == cur_block: i += 1 continue swap_to = next_free[radix_val] a_list[i], a_list[swap_to] = a_list[swap_to], a_list[i] next_free[radix_val] += 1 #   def american_flag_sort_helper(a_list, start: int, end: int, digit, radix) -> None: #          offsets = compute_offsets(a_list, start, end, digit, radix) #      swap(a_list, offsets, start, end, digit, radix) if digit == 0: #     ? return #   #       for i in range(len(offsets)-1): #      #         american_flag_sort_helper(a_list, offsets[i], offsets[i+1], digit-1, radix) #   def american_flag_sort(a_list, radix) -> None: #,         for x in a_list: assert(type(x) == int) #    max_val = max(a_list) #    (  ) max_digit = int(floor(log(max_val, radix))) #   -     american_flag_sort_helper(a_list, 0, len(a_list), max_digit, radix)

سكا فرز :: سكا فرز


أعلن المبرمج الألماني Malte Skarupke أنه طور خوارزمية فرز جديدة ، وهي عبارة عن "علم أمريكي" محسّن بشكل جذري وتتفوق على std :: sort في المتوسط ​​2 مرات (std :: sort - خوارزمية تعرف أيضًا باسم الفرز الاستبطاني - مزيج من الفرز السريع والفرز بواسطة كومة ).

  1. يتم فرز المصفوفة بشكل متكرر ، في المستوى الأول من العودية ، يتم أخذ المصفوفة بأكملها كخلفية فرعية.
  2. إذا كانت الطبقة الفرعية تحتوي على أقل من 128 عنصرًا ، فسيتم استدعاء std :: sort لذلك.
  3. إذا كانت الطبقة الفرعية تحتوي على عناصر من 128 إلى 1024 ، فسيتم استدعاء تصنيف العلم الأمريكي لذلك.
  4. إذا كان هناك أكثر من 1024 عنصرًا في صفيف فرعي ، فسيتم استدعاء فرز ska لذلك.
  5. أيضًا ، لتجنب أسوأ الحالات ، إذا كان التداخل التكراري كبيرًا جدًا (أكثر من 16 مستوى) ، فإن الخوارزمية تنتقل إلى std :: sort ، حتى إذا كان هناك أكثر من 128 عنصرًا في المصفوفة الفرعية.

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

مراجع


العلم الهولندي مشكلة العلم ، العلم الأميركي نوع

سكا نوع: كتبت خوارزمية فرز أسرع ( الجزء 1 ، الجزء 2 ) كود جيثب

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


في تطبيق AlgoLab Excel ، الفرز حسب علم بلونين (فرز الأصفار والأخرى) ، ظهرت علامة ثلاثية الألوان (فرز الأصفار ، والأزواج ، والفروع) ، والفرز حسب العلم الأمريكي. لفرز "العلم الأمريكي" ، يمكنك (في تعليق على الخلية باسم الخوارزمية) تحديد نظام الأرقام للتوزيع - الافتراضي هو ست عشرية.

Source: https://habr.com/ru/post/ar481304/

More articles:


All Articles