الترتيب بالدمج

في القسم 14.3، شاهدنا خوارزمية ترتيب بسيطة تبين فيما بعد أنها غير فعالة حقاً. لترتيب n عنصر، عليها عبور المصفوفة n مرة، وكل عبور يستهلك كمية من الزمن تتناسب مع n. وهو ما يؤدي إلى أن الزمن الكلي المستغرق يتناسب مع n2.
في هذا القسم سأشرح خوارزمية أكثر فعالية تدعى الترتيب بالدمج (mergesort). لترتيب n عنصر، تستهلك خوارزمية الترتيب بالدمج زمناً يتناسب مع n.log(n). قد لا يبدو هذا مبهراً، لكن عندما يكبر n، فإن الفرق بين n2 وn.log(n) قد يكون شاسعاً. جرب بضعة قيم لـ n وانظر بنفسك.
إن الفكرة الأساسية للترتيب بالدمج هي: إذا كنت تملك مجموعتين فرعيتين، وكل منهما قد تم ترتيبها، فسيكون سهلاً (وسريعاً) أن تدمجهما في مجموعة واحدة مرتبة. جرب هذه مع مجموعة ورق شدة:
1. شكل مجموعتين فرعيتين من 10 أوراق تقريباً لكل منهما ورتبها بحيث تكون الورقة الأدنى في البداية عندما يكون وجه الأوراق إلى الأعلى. ضع المجموعتين أمامك ووجههما إلى الأعلى.
2. قارن بين الأوراق الأولى من كل مجموعة واختر الأدنى بينهما. اقلبها وأضفها إلى المجموعة المدمجة.
3. أعد الخطوة 2 حتى تنتهي إحدى المجموعتين. ثم خذ الأوراق الباقية وأضفها إلى المجموعة المدمجة.
يجب أن تكون النتيجة مجموعة واحدة مرتبة. هذا هو ما ستبدو عليه الخوارزمية باستخدام الشفرة الزائفة:
كود:
public static Deck merge(Deck d1, Deck d2) {
   // create a new deck big enough for all the cards
   Deck result = new Deck(d1.cards.length + d2.cards.length);
 
   // use the index i to keep track of where we are in
   // the first deck, and the index j for the second deck
   int i = 0;
   int j = 0;
 
   // the index k traverses the result deck
   for (int k = 0; k<result.cards.length; k++) {
 
      // if d1 is empty, d2 wins; if d2 is empty, d1 wins;
      // otherwise, compare the two cards
 
      // add the winner to the new deck
   }
   return result;
}
أفضل طريقة لاختبار merge هي إنشاء مجموعة ورق وخلطها، واستعمال subdeck لتشكيل مجموعتين فرعيتين (صغيرتين)، ثم استعمال عملية الترتيب من الفصل السابق لترتيب القسمين. ثم يمكنك تمرير هذين القسمين إلى merge لترى إذا كانت ستعمل.
إذا استطعت جعلها تعمل، جرب كتابة شكل بسيط للعملية mergeSort:
كود:
public static Deck mergeSort(Deck deck) {
   // find the midpoint of the deck
   // divide the deck into two subdecks
   // sort the subdecks using sortDeck
   // merge the two halves and return the result
}
بعد ذلك، إذا تمكنت من جعل تلك النسخة تعمل، يبدأ المرح الحقيقي! الشيء السحري في الترتيب بالدمج هو أنه تعاودي. عند ترتيب المجموعتين الجزئيتين، لم علينا استدعاء النسخة القديمة والبطيئة من sort؟ لم لا نستدعي العملية الجديدة الأنيقة mergeSort التي تكتبها الآن؟
هذه ليست مجرد فكرة جيدة، بل هي ضرورية للحصول على التحسن في الأداء الذي وعدتك به. لكن حتى تعمل عليك أن تملك حالة قاعدية؛ وإلا فسوف تستمر العملية بالتعاود للأبد. يمكن أن نعتبر مجموعة فرعية من ورقة واحدة أو مجموعة لا تحوي أوراق كحالة قاعدية بسيطة. إذا استقبلت mergeSort مجموعة صغيرة كهذه، يمكن لها أن تعيدها مباشرة، لأنها مرتبة أصلاً.
ستبدو النسخة التعاودية من mergeSort مثل هذه:
كود:
public static Deck mergeSort(Deck deck) {
   // if the deck is 0 or 1 cards, return it
 
   // find the midpoint of the deck
   // divide the deck into two subdecks
   // sort the subdecks using mergesort
   // merge the two halves and return the result
}
كالعادة، توجد طريقتين للتفكير بالبرامج التعاودية: يمكنك تتبع مجرى التنفيذ كله، أو يمكنك القيام "بوثبة الثقة". لقد بنيت هذا المثال لأشجعك على "القفز بثقة".
عند استعمال sortDeck لترتيب المجموعات الفرعية، لن تشعر أنك مضطر لتتبع مسار التنفيذ، صحيح؟ ستفترض أنها تعمل بشكل صحيح لأنك نقحتها من الأخطاء مسبقاً. حسناً، كل ما فعلته لجعل mergeSort تتعاود هو استبدال خوارزمية الترتيب بواحدة أخرى. لا يوجد أي سبب يدعوك لقراءة البرنامج بشكل مختلف.
في الواقع، عليك التفكير قليلاً بالحالة القاعدية والتأكد من أنك ستصل إليها في النهاية، لكن فيما عدا ذلك، يجب ألا تكون كتابة النسخة التعاودية مشكلة على الإطلاق. حظاً طيباً!