البحث والترتيب العوديان
| English | العربية |
|---|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | القسمة والتغلب |
| merge sort/mɜːdʒ sɔːt/ | فرز الدمج |
| merge/mɜːdʒ/ | اندماج |
التراجع يقابل البحث والفرز
- نفس مبدأ التقسيم والحل powering الـ بحث الثنائي التراجعي وفرز الدمج.
- نقسم المشكلة لنصفين، نحل النصفين، ثم ندمجهما.
- البحث الثنائي التراجعي يبحث في نصف واحد عن طريق استدعاء نفسه عليه.
- فرز الدمج يرتب كل نصف، ثم يدمج نصفي المرتبين معاً.
البحث الثنائي التراجعي
- الحالة الأساسية: نطاق فارغ يعني أن الهدف لم يتم العثور عليه.
- انظر إلى الوسط. إذا كان هو الهدف، أدرج مؤشره.
- إذا كان الهدف أصغر، استمر تراجعيًا في النصف الأيسر؛ إذا كان أكبر، النصف الأيمن.
- كل استدعاء يخفض النصف — نفس الرتبة
O(log n)، مكتوبة بتراجع.
فرز الدمج
- قسّم المصفوفة لنصفين؛ رتّب كل نصف تراجعيًا.
- الحالة الأساسية: مصفوفة بحجم 0 أو 1 عنصر هي مرتبة بالفعل.
- الدمج: مر على نصفي المرتبين، وأخذ العنصر الصغير من المقدمة دائمًا.
- أسرع بكثير من فروز
n²— حواليn log nعمل.
لماذا يفوز التقسيم والحل
- تخفيض المشكلة بالنصف في كل خطوة يعطي معامل
log n. - فرز الدمج برتبة
n log nيتفوق على فرز الاختيار/الإدراج برتبةn²على المصفوفات الكبيرة. - الحالة الأساسية (فارغة أو عنصر واحد) توقف كل فرع.
- نفس الشكل الخاص بالتراجع: تقسيم للأسفل، ودمج للأعلى.
البحث الثنائي التراجعي يستمر تراجعيًا في نصف واحد (الهدف موجود في جانب واحد فقط)؛ فرز الدمج يستمر تراجعيًا في كلا النصفين ثم يدمجهما. كلاهما يحتاج لحالة أساسية — نطاق فارغ يعني "لم يتم العثور عليه" للبحث؛ مصفوفة بحجم 0 أو 1 عنصر مرتبة بالفعل لفرز الدمج. التقسيم والحل هو ما يجعلهما سريعين (O(log n) وO(n log n)).
فرز الدمج لمصفوفة ثنائية الأبعاد [3, 1, 2, 4]:
- قسّمها إلى
[3, 1]و[2, 4]؛ صنف كل جزء →[1, 3]و[2, 4]. - الدمج: خذ 1، ثم 2، ثم 3، ثم 4 →
[1, 2, 3, 4]. - في كل عملية دمج، يتم اختيار العنصر الأصغر من المقدمة على التوالي.
البحث الثنائي المتكرر يعيد التكرار على نصف واحد (الحالة الأساسية: نطاق فارغ = غير موجود) للبحث O(log n). ترتيب الدمج يعيد التكرار على كلا النصفين ويدمجهما (الحالة الأساسية: عنصر 0 أو 1) للترتيب O(n log n). كلاهما تقسيم وحل: التقسيم للأسفل، والجمع للأعلى — أسرع بكثير من n².
دمج الترتيب يُقسم إلى نصفين، ثم يدمج لأعلى
العناصر المفردة مرتبة (الحالة الأساسية)؛ الدمج يجمعها لأعلى.
البحث الثنائي العودي يعيد الاستدعاء على...
الهدف موجود على جانب واحد فقط من المنتصف.
دمج الترتيب يعيد الاستدعاء على...
رتب كل نصف، ثم ادمج نصفي الترتيب.
الحالة الأساسية لدمج الترتيب هي مصفوفة من...
عنصر واحد (أو صفر) لا يحتاج لترتيب.
وقت تشغيل دمج الترتيب هو حوالي...
log n مستويات للتقسيم، عمل n في كل مستوى.
كلا البحث الثنائي العودي ودمج الترتيب هما خوارزميات قسم وحكم.
كلاهما يقسم المشكلة لنصفين ويعيد الاستدعاء.
رتب خطوة الدمج للنصفين [1,3] و [2,4].
اختر دائماً العنصر الأصغر أمامك: 1، 2، 3، 4.