في التعليقات على المقالات السابقة ، هناك أحيانًا عتاب - لماذا حتى تدرس أي تصنيفات أخرى ، إذا كان هناك بالفعل أسرع فرز سريع في العالم. يقولون أن كل هذا الغريب الخيالي لا فائدة منه ولا يحتاجه أحد.
يعتقد بيرسي دياكونيس ، الذي درس تصنيف سوليتير على طول وعبر ، أنها أسرع طريقة لترتيب مجموعة من البطاقات يدويًا.
لذا ، إذا لم يكذب عالم رياضيات محترم (وساحر بطاقة من ذوي الخبرة) ، فعندئذ مع القيمة العملية للخوارزمية ، كل شيء في محله.
شاهد الآن يديك.
المرحلة الأولى
لذا ، خذ الديدان من سطح السفينة. ستمثل مجموعة من ثلاثة عشر عنصرًا عشوائيًا.
نحتاج إلى تفكيك البطاقات إلى عدة أكوام ، بحيث تكون كل مجموعة تسلسلاً منظمًا في كل كومة.
بمعنى آخر ، مهمتنا في هذه المرحلة هي إنشاء عدة مصفوفات فرعية مرتبة من الصفيف الحالي غير المصنف. في نفس الوقت ، من المستحسن للغاية أن يكون عدد هذه المصفوفات الفرعية أصغر ، مما يعني أنك بحاجة إلى السعي لضمان أن المصفوفات الفرعية أكثر واقعية. يتم ذلك على النحو التالي.
البطاقة الأولى هي بداية الكومة الأولى.
نقوم بنقل البطاقات إلى هذا الكومة بدورها ، حتى تصبح البطاقة المنقولة التالية أصغر من البطاقة الأولى في الكومة.
علاوة على ذلك ، كل مكدس هو مكدس - نحن لا نعمل مع المكدس بأكمله ، ولكن فقط مع البطاقة العليا فيه ، والتي تم وضعها في النهاية.
إذا كانت البطاقة الحالية أكبر من الحد الأدنى في المكدس ، فعليك إنشاء كومة جديدة ، فتفتح البطاقة الحالية مكدسًا جديدًا.
ترتيب المداخن مهم! إذا كان عددهم بالفعل أكثر من واحد ، فإننا نضع البطاقة التالية ليس في الكومة الأخيرة ، ولكن في كومة اليسار ، حيث يمكننا وضعها.
الآن ، بعد السيدة ، أحتاج إلى إرفاق تسعة في مكان ما. من الناحية الميكانيكية ، أريد أن أضع البطاقة في الكومة الثانية ، لكن في الكومة الأولى تكون البطاقة العلوية أكثر من تسعة. لذا ، يمكننا الاستمرار في المكدس الأول دون انتهاك أمره. الثلاثة التالية ، التي تتبع التسعة ، بالمناسبة ، تذهب إلى الكومة الأولى.
لا يمكن إضافة سبعة وستة إلى الكومة الأولى (فهي أكبر من الورقة العليا فيها) ، ولكن لا يزال لديهم مكان في الكومة الثانية.
يبدأ Ace كومة جديدة. يقع التافه المتبقي في صواني مختلفة ، اعتمادًا على مدى اليسار إلى المكدس حيث يمكن إدخاله.
ونتيجة لذلك ، تم وضع البطاقات في عدة أكوام. في كل كومة ، البطاقات عبارة عن تسلسل تنازلي ، في الأعلى هي أصغر بطاقة. الأكوام هي أكوام.
نظرًا لأننا حاولنا أولاً تعبئة المكدسات الموجودة على اليسار ، فقد شكلنا أصغر كمية ممكنة. إذا مشينا للتو عبر الصفيف واستخرجنا المصفوفات الفرعية المتناقصة منه ، فإن الكومة ستصبح أكبر بشكل طبيعي.
المرحلة 2. الصف السفلي
انقل البطاقات العلوية المتاحة إلى الأسفل قليلاً حتى تقف في صف منفصل. إذا كانت المكدسات هي مكدسات ، فسوف نعمل مع الصف السفلي كما هو الحال مع قائمة الانتظار.
الأهم من ذلك ، فإن البطاقات العلوية المتاحة في الأكوام هي أيضًا تسلسل منظم. تم فرز الصف السفلي بترتيب تصاعدي بالفعل. وهذا ليس مفاجئًا - عند تشكيل مجموعات من البطاقات ، تم إرسال بطاقات أصغر إلى اليسار.
في المستقبل ، حتى نهاية الفرز ، لسنا مهتمين بجميع البطاقات الموضوعة على الطاولة. هذه فقط مطلوبة:
- البطاقة الموجودة في أقصى اليسار (لنطلق عليها البطاقة الحالية) في الصف السفلي من قائمة الانتظار.
- في مكدسات الأكوام ، نعمل فقط مع أفضل البطاقات المتاحة. في هذه الحالة ، هناك حاجة فقط للأكوام الموجودة مباشرة على الخريطة الحالية وإلى اليسار. ليست هناك حاجة لأكوام إلى اليمين في هذه اللحظة.
في الصف السفلي ، نقوم بفرز البطاقات من اليسار إلى اليمين للبطاقة. أقصى اليسار هو الحد الأدنى الحالي ، ونعيده إلى الصف العلوي الأصلي. في نفس الوقت ، في كل مرة نعود فيها إلى القاعدة بطاقة أخرى ، من الضروري وضع بطاقة أخرى في مكانها. من أين تحصل عليه؟ من بين الأكوام الموجودة أعلى الخريطة الحالية وإلى يسارها - من بين البطاقات المتاحة ، يتم تحديد الحد الأدنى الذي ينتقل إلى الموضع الشاغر للبطاقة اليسرى الحالية في الصف السفلي ، ومن هناك إلى الصفيف الرئيسي.
يعود اثنان في الصفيف على الفور. يتم أخذ المكان الذي تم إخلاؤه بواسطة الثلاثي (نقوم بنقله من الكومة الأولى إلى الصف السفلي) ، ومن الصف السفلي ، ينتقل الثلاثي كحد أدنى إلى الصفيف الرئيسي. في الأكوام الأولين ، يتم البحث عن الحد الأدنى مرة أخرى - وهذا هو الأربعة - الذي يعود أيضًا إلى المنزل. يصبح خمسة الحد الأدنى الحالي ، إلخ.
من خلال الجمع بين العمل بترتيب تصاعدي لقائمة الانتظار وترتيب تنازلي للمكدسات بسرعة كبيرة ، نحصل على جميع العناصر من الحد الأدنى إلى الحد الأقصى. شيء من هذا القبيل بشكل عام.
الرسوم المتحركة لهذه العملية.
إذا قمت بترجمة كل ما سبق إلى Python ، فستحصل على هذا:
from functools import total_ordering from bisect import bisect_left from heapq import merge @total_ordering class Pile(list): def __lt__(self, other): return self[-1] < other[-1] def __eq__(self, other): return self[-1] == other[-1] def patience_sort(n): piles = []
المراجع
فرز الصبر (
ترجمة جوجل )
مصدر فرز الصبر
برينستون CS: أطول مدة متتالية مجموعات من أكوام فرز الصبر (
ترجمة جوجل )
ملخصات ويكي: فرز المرضىمحاذاة الكلمة (
ترجمة جوجل )
سلسلة المقالات:
في تطبيق AlgoLab ، هذا الفرز نشط الآن. في نفس الوقت ، فإن التصور ممكن في وضعين: في شكل خرائط (الوضع الافتراضي) وببساطة في شكل أرقام. ومع ذلك ، بالنسبة لأسلوب البطاقة ، من الضروري أن يكون الفرق بين الحد الأقصى والحد الأدنى للعناصر في المصفوفة أقل من 54 (عدد البطاقات في المجموعة ، بما في ذلك اثنين من الجوكر). إذا لم يتم استيفاء هذا الشرط أو تم إيقاف تشغيل وضع البطاقة تمامًا (لهذا ، تحتاج إلى كتابة بطاقة = 0 في التعليق للخلية باسم الفرز) ، فسيكون التصور في شكل أرقام باهتة.
يتم النظر في الدعاوى حسب ترتيب الأقدمية:
القمم <الأندية <الدف> <القلوب.أي أن بطاقة بدلة الدف من الدف أكبر من
أي بطاقة بدلة نادي ،
أي بطاقة بدلة قلوب أكبر من
أي بطاقة بدلة ذروة ، إلخ. إذا رسمنا تشابهًا بالأرقام ، فإن القمم من 0 إلى 9 ، والنوادي من 10 إلى 19 ، والماس من 20 إلى 29 ، والقلوب من 30 إلى 39 (نعم ، بالطبع ، داخل البدلة ، عدد البطاقات ليس بالضبط عشرة ، ولكن أنت تفهم ما هو المقصود). أما الأقدمية
في الدعوى ، فستكون عادية: من الإله إلى الآس. يمكنك أيضا أن تأخذ الفتيان الذين هم أكبر سنا من جميع البطاقات الأخرى. في هذه الحالة ، الجوكر الأحمر أكثر ثقلًا من الأسود.
تمت كتابة هذه المقالة بدعم من EDISON Software ، وهي شركة تطوير ويب احترافية أعادت تصميم موقعها على الويب مؤخرًا .