Recursive Searching and Sorting
مُقدَّم| English | المعنى |
|---|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | فرق تسد |
| merge sort/mɜːdʒ sɔːt/ | فرز الدمج |
| merge/mɜːdʒ/ | دمج |
التراجع يقابل البحث والفرز
- نفس مبدأ القسمة والتحصيل يدير البحث الثنائي المتكرر وفرز الدمج.
- نقسم المشكلة لنصفين، نحل النصفين، ثم ندمجهما.
- البحث الثنائي التراجعي يبحث في نصف واحد عن طريق استدعاء نفسه عليه.
- فرز الدمج يرتب كل نصف، ثم يدمج نصفي المرتبين معاً.
البحث الثنائي التراجعي
- الحالة الأساسية: نطاق فارغ يعني أن الهدف لم يتم العثور عليه.
- انظر إلى الوسط. إذا كان هو الهدف، أدرج مؤشره.
- إذا كان الهدف أصغر، استمر تراجعيًا في النصف الأيسر؛ إذا كان أكبر، النصف الأيمن.
- كل استدعاء يخفض النصف — نفس الرتبة
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².
Merge sort splits into halves, then merges up
Single elements are sorted (base case); merges combine them upward.
Recursive binary search recurses on...
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
The target is only on one side of the middle.
Merge sort recurses on...
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Sort each half, then merge the two sorted halves.
The base case for merge sort is an array of...
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
One (or zero) element needs no sorting.
Merge sort's running time is about...
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
log n levels of splitting, n work per level.
Both recursive binary search and merge sort are divide-and-conquer algorithms.
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Both split the problem in half and recurse.
Order the merge step for halves [1,3] and [2,4].
الصعوبة 3/5 · 200 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Always take the smaller front element: 1, 2, 3, 4.