دمج أنواع العمل وفقًا لهذا المبدأ:
- يتم البحث عن المصفوفات الفرعية المطلوبة (كخيار - يتم تكوينها).
- يتم تجميع السلاسل الفرعية المرتبة في طبقة فرعية مرتبة شائعة.
في حد ذاته ، فإن أي ترتيب فرعي مرتب داخل الصفيف لا يحتوي على قيمة كبيرة. ولكن إذا وجدنا في صفيفين
صفحتين فرعيتين مرتبة ، فهذا أمر مختلف تمامًا. الحقيقة هي أنه يمكنك دمجها بسرعة كبيرة وبأقل تكلفة - لتكوين صفيف فرعي عام مرتب من زوج من المصفوفات الفرعية المطلوبة.
كما ترى ، فإن الجمع بين صفيفين مرتبتين في واحدة ليس بالأمر السهل ، ولكنه بسيط للغاية. تحتاج إلى التحرك في نفس الوقت في كلا الصفيفين من اليسار إلى اليمين ومقارنة الأزواج التالية من العناصر من كلا الصفيفين. يتم إرسال العنصر الأصغر إلى المرجل المشترك. عندما تنتهي العناصر في إحدى الصفائف ، يتم ببساطة نقل العناصر المتبقية من الصفيف الآخر إلى القائمة الرئيسية بالترتيب.
هذا هو ملح الخوارزميات من هذه الفئة. في البداية ، يمكن تقسيم مجموعة عشوائية إلى العديد من المصفوفات الفرعية الصغيرة المرتبة. في الدمج المزدوج ، يتناقص عدد المصفوفات الفرعية المطلوبة ، ويزداد طول كل منها. في الخطوة الأخيرة ، يتكون الصفيف من اثنين من المصفوفات الفرعية المرتبة التي يتم دمجها في بنية مرتبة واحدة.
مؤلف هذا المفهوم هو جون فون نيومان. في بعض الأحيان ، هناك ادعاء مثير للجدل بأنه توصل للفرز أثناء العمل في مشروع مانهاتن ، حيث واجه مهمة تقديم حسابات فعالة لكمية هائلة من البيانات الإحصائية في تطوير قنبلة نووية. من الصعب تقييم مصداقية هذا الإصدار ، حيث يرجع تاريخ أول عمل له في الفرز حسب الدمج إلى عام 1948 ، وتم الانتهاء من إنشاء القنبلة قبل 3 سنوات. ومع ذلك ، ما هو نوع الفرز الذري الموجود ، دعونا نلقي نظرة عليه.
نيومان الطبيعية الانصهار
تأثرت خوارزمية نيمان بميزات تصميم أجهزة الكمبيوتر في الأربعينات. يبدو مثل هذا:
- في المجموع ، يتم استخدام ثلاثة أشرطة مغناطيسية - الشريط الرئيسي ، حيث يتم تسجيل البيانات غير المصنفة والبيانات المساعدة.
- تتم قراءة البيانات بالتسلسل من الشريط الرئيسي.
- على الرغم من أن البيانات المقروءة بالتسلسل هي عبارة عن طبقة فرعية مرتبة ، إلا أنه يتم نسخها إلى أحد الأشرطة المساعدة.
- بمجرد اكتمال الصفيف الفرعي التالي (على سبيل المثال ، يوجد عنصر أصغر من العنصر السابق في الشريط الرئيسي) ، يتم وضع مؤشر على الشريط الإضافي (نهاية الصفيف الفرعي) ويحدث التحول إلى شريط إضافي مساعد.
- يتم تكرار النقاط 2-4 مرة أخرى ، ويتم نقل البيانات فقط إلى شريط مساعد آخر. في نهاية المجموعة الفرعية المطلوبة التالية ، ينتقل الشريط الرئيسي بالتناوب إلى شريط إضافي ، ثم إلى شريط آخر.
- عند قراءة جميع البيانات من الشريط الرئيسي ، تتم معالجة الأشرطة المساعدة.
- يقوم كل من الأشرطة المساعدة بقراءة البيانات بدورها.
- في هذه الحالة ، تتم مقارنة البيانات التالية من شريطين مع بعضهما البعض. وفقًا لنتائج المقارنة ، يتم تسجيل أصغر عنصر في الزوج على الشريط الرئيسي.
- نظرًا لأن حدود المصفوفات الموجودة على الأشرطة المساعدة محددة بالمؤشرات ، فإن القراءة والمقارنة تحدث فقط داخل المصفوفات الفرعية المصنفة.
- في حالة انتهاء أحد العناصر الفرعية الموجودة على أحد الأشرطة المساعدة ، فحينئذٍ يتم نقل الجزء المتبقي من المصفوفة الفرعية من الشريط المتبقي إلى الشريط الرئيسي.
- نكرر العملية بأكملها مرة أخرى حتى تكون البيانات الموجودة على الشريط الرئيسي عبارة عن مجموعة مرتبة بالكامل.
الفرز نيومان هو خوارزمية تكيفية: فهو لا يعمل فقط على إصلاح الأجزاء المصنفة من المصفوفة ، ولكن أيضًا يحاول أولاً زيادة هذه المصفوفات ، بحيث تقوم على أساس المصفوفات الفرعية المرتبة المطولة بتكوين صفائف فرعية مرتبة أطول. لذلك ، يطلق عليه أيضًا
دمج دمج الفرز .
تعقيد هذه الخوارزمية هو متواضع - O (
ن 2 ) ، ومع ذلك ، بالنسبة لرواد الحوسبة الأنبوبية ، كان هذا اختراقًا.
في مثال هذا النوع من الدمج الأول ، يكون عيب هذه الفئة من الخوارزميات مرئيًا بالفعل - تكلفة الذاكرة الإضافية. في هذا الصدد ، تتطلب جميع عمليات دمج الدمج تقريبًا إضافة إلى O (
n ) ، ومع ذلك ، فإن الاستثناءات الأنيقة نادرة.
باوز نيلسون الاندماج المباشر
بالمعنى الدقيق للكلمة ، خوارزمية Bowes-Nelson هي شبكة فرز ، وليس فرز. في هذه العملية ، يتم تقسيم المصفوفة وجميع المصفوفات الفرعية إلى نصفين ولا شيء يمنع معالجة كل هذه النصفين بشكل متوازٍ في جميع المراحل. ومع ذلك ، يمكن أيضا أن تكون ممثلة في شكل الفرز. وسنتطرق إلى موضوع فرز الشبكات أيضًا.
- تنقسم المجموعة إلى نصفين - إلى النصفين الأيسر والأيمن.
- تنقسم العناصر إلى مجموعات.
- في التكرار الأول ، هذان هما العنصران (العنصر الأول للنصف الأيسر + العنصر الأول للنصف الأيمن ، العنصر الثاني للنصف الأيسر + العنصر الثاني للنصف الأيمن ، إلخ) ، عند التكرار الثاني - العناصر الأربعة (1- العناصر الثانية والثانية للنصف الأيسر + العناصر الأولى والثانية للنصف الأيمن ، والعنصر الثالث والرابع للنصف الأيسر + العناصر الثالثة والرابعة للنصف الأيمن ، إلخ) ، على العنصر الثالث - الثمانيات ، الخ
- عناصر من كل مجموعة من النصف الأيسر يتم فرزها ، كما يتم فرز عناصر من كل مجموعة من النصف الأيمن من المصفوفات الفرعية.
- دمج المصفوفات الفرعية المصنفة من الفقرة السابقة.
- نعود إلى النقطة 1. تستمر الدورة حتى تصبح أحجام المجموعات أصغر من حجم المصفوفة.
قد يبدو أن الذاكرة الإضافية مطلوبة هنا. لكن لا! للحصول على تصور أكثر قابلية للفهم في الرسوم المتحركة ، يوجد النصفان الأيسر والأيمن للصفيف على بعضهما البعض ، بحيث يكون الموضع النسبي للصفحات الفرعية المقارنة أكثر وضوحًا. ومع ذلك ، نظرًا للتقسيم الصارم ، يمكن إجراء خوارزمية يتم فيها إجراء جميع المقارنات والتبادلات دون الحاجة إلى موارد إضافية من الذاكرة. وهو أمر غير معتاد للغاية بالنسبة لفرز الدمج.
def bose_nelson(data): m = 1 while m < len(data): j = 0 while j + m < len(data): bose_nelson_merge(j, m, m) j = j + m + m m = m + m return data def bose_nelson_merge(j, r, m): if j + r < len(data): if m == 1: if data[j] > data[j + r]: data[j], data[j + r] = data[j + r], data[j] else: m = m // 2 bose_nelson_merge(j, r, m) if j + r + m < len(data): bose_nelson_merge(j + m, r, m) bose_nelson_merge(j + m, r - m, m) return data
هناك شيء في جميع عمليات دمج الفرز تجعلها تشبه القنبلة الهيدروجينية. يحدث الانقسام الأول ، ثم التوليف.
المراجع
دمج /
دمجسلسلة المقالات:
كل من الفرز المذكورة في مقالة اليوم متاحة الآن في تطبيق AlgoLab (لأولئك الذين يدرسون الخوارزميات باستخدام تطبيق Excel هذا ، قم بتحديث الملف). وفي غضون يومين فقط ، مع إصدار تتمة قادمة على أنواع الدمج ، ستتوفر عدة خوارزميات أخرى من هذه الفئة.
يوجد قيد لفرز Bowes-Nelson - يجب أن يكون حجم المصفوفة قوة لاثنين. إذا لم يتم استيفاء هذا الشرط ، فسيحذف الماكرو الصفيف إلى حجم مناسب.
كُتب هذا المقال بدعم من EDISON Software ، وهي شركة تكتب برامج إعادة الإعمار ثلاثية الأبعاد وتقوم بتطوير أجهزة قياس متطورة .