في المقالة الأخيرة ، تعرفنا على أنواع الدمج المرحلي (مما تسبب في الاهتمام التاريخي في المقام الأول). ما هو الاتجاه اليوم؟

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

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

نحتاج ، في الواقع ، إلى دمج نصفين من المقطع في طبقة فرعية واحدة. يتم فرز النصفين في وقت واحد في صفيف واحد ، وتتم مقارنة العناصر الحالية في كلتا التكرار ، ويذهب العنصر الأصغر إلى الصفيف الثاني:

//   A[iBegin: iMiddle - 1] //   A[iMiddle: iEnd - 1] //:   B[iBegin: iEnd - 1] void Merge(A[], iBegin, iMiddle, iEnd, B[]) { i = iBegin, j = iMiddle; //       ... for (k = iBegin; k < iEnd; k++) { //     //  <=    if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) { B[k] = A[i]; i++; } else { B[k] = A[j]; j++; } } } 

نسخ قطعة من مجموعة واحدة إلى أخرى. يعمل كلا التطبيقين على صفيفين ، يجب أن يتم نقل البيانات باستمرار من الرئيسي إلى المساعد والعكس بالعكس:

 //    A[] //   B[] void CopyArray(A[], iBegin, iEnd, B[]) { for(k = iBegin; k < iEnd; k++) B[k] = A[k]; } 

تنازليا الاندماج المتوازن

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

 //  A[]     // B[]   void TopDownMergeSort(A[], B[], n) { CopyArray(A, 0, n, B); // A[]  B[] TopDownSplitMerge(B, 0, n, A);// B[]    A[] } //    A[],  B[]    // : iBegin ; iEnd   void TopDownSplitMerge(B[], iBegin, iEnd, A[]) { // size == 1,     if(iEnd - iBegin < 2) return; // size > 1,     iMiddle = (iEnd + iBegin) / 2;//iMiddle -   //     A[]  B[] TopDownSplitMerge(A, iBegin, iMiddle, B);//   TopDownSplitMerge(A, iMiddle, iEnd, B);//   //    B[]  A[] Merge(B, iBegin, iMiddle, iEnd, A); } 

متوازن الاندماج التصاعدي

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

 //  A[]     // B[]   void BottomUpMergeSort(A[], B[], n) { //      A[]  «». //    : //× 2, 4, 8, 16, ... -   ,       for (width = 1; width < n; width = 2 * width) { //     width for (i = 0; i < n; i = i + 2 * width) { //   : //A [i: i + width - 1]  A [i + width: i + 2 * width - 1]  B[] //  A[i: n - 1]  B[] ( i + width > = n) Merge(A, i, min(i + width, n), min(i + 2 * width, n), B); } //   B[]    2 * width //  B[]   A[]    //     A[]  B[] CopyArray(B, 0, n, A); // B[]  A[] //      2 * width } } 

بشكل عام ، يُفضل تنفيذ من أعلى لأسفل ، لأنه يستخدم صفيفين بشكل أكثر كفاءة ، مما يؤدي ببساطة إلى تغيير أدوار "الرئيسي / المساعد". في الإصدار الأساسي ، يكون الصفيف A دائمًا أساسيًا ، وتكون الصفيف B دائمًا مساعدة. نتيجة لذلك ، بعد كل تكرار ، يجب إعادة البيانات من B بالكامل إلى A ، والتي لا تسهم في تحسين تعقيد الخوارزمية. من ناحية أخرى ، فإن تنفيذ الصعود أبسط ؛ فهو لا يحتوي حتى على العودية.

الاندماج غير المتوازن

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

في الواقع ، الأمر أسوأ. بطبيعة الحال ، فإن تقسيم المصفوفات الفرعية إلى نصفين متساويين (وهو ما يعني التوازن بين أنواع الدمج) أسهل في التنفيذ. قسّم نفسك الصفيف إلى النصف وطبق العودية على كل شوط. في الواقع ، هذه السهولة هي الميزة الرئيسية لعملية دمج متوازنة قبل واحدة غير متوازنة.

في المنشورات التالية ، سننظر في أساليب غير متوازنة. فهي أكثر صعوبة بشكل ملحوظ لفهم وتنفيذ. لن يتم توزيع بيانات الدمج اللاحقة بالتساوي والتساوي عبر المصفوفات المساعدة ، ولكن وفقًا لعدد من أرقام فيبوناتشي المعممة. وهذا سيسمح لك بتحقيق نتائج قوية لا يمكن تحقيقها لطرق متوازنة مبسطة.

المراجع

دمج ( ترجمة جوجل ) ، دمج

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

• تطبيق اكسل AlgoLab.xlsm
• أنواع التبادل
• أنواع الإدراج
• الترتيب حسب الاختيار
• دمج الأنواع
  
  • دمج متوازن من أعلى إلى أسفل ومن الأسفل إلى الأعلى
  • ترتيب دمج المراحل المتعددة
  • ترتيب دمج المتتالية
  • ترتيب دمج تتأرجح
  • الفرز الخيوط وغير القابلة للامتزاج
  • دمج مقارنة الفرز
• الترتيب حسب التوزيع
• الفرز الهجين

تتوفر الفرز دمج التالية الآن في تطبيق AlgoLab (لأولئك الذين يدرسون الخوارزميات باستخدام تطبيق Excel هذا ، قم بتحديث الملف).

المصفوفات محدودة مؤقتًا - يجب أن يكون حجمها قوة لاثنين (بسبب بعض الصعوبات التي واجهتها عند برمجة التصور). بعد ذلك بقليل سيكون من الممكن فرز أي صفائف.

كُتب هذا المقال بدعم من EDISON Software ، وهي شركة تستخدم الخدمات السحابية لإنشاء برامج مدمجة وتطوير تطبيقات الهاتف المحمول على JAVA .