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

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

نصفان مرتبان من قائمة منقولان إلى صف المخزن المؤقت، والقيمة الأولى الأصغر تصعد عائدةً إلى القائمة
نصفان مرتبان من قائمة منقولان إلى صف المخزن المؤقت، والقيمة الأولى الأصغر تصعد عائدةً إلى القائمة

الفكرة

الدمج هو الجزء السهل. إذا كانت لديك قائمتان كل منهما مرتبة، فقارن قيمتيهما الأوليين وخذ الأصغر. ثم قارن القيمتين الأوليين الجديدتين وخذ الأصغر مرة أخرى. وعندما تنفد إحدى القائمتين، ألحق باقي الأخرى. كل خطوة تأخذ قيمة واحدة، لذا يحتاج دمج قائمتين طولهما الكلي m إلى m − 1 مقارنة على الأكثر. ويستخدم الترتيب بالدمج ذلك للترتيب: قسّم القائمة إلى نصفين، ورتّب كل نصف بالترتيب بالدمج، ثم ادمج النصفين.

مثال

خذ 5, 1, 4, 2, 8. قسّمها إلى 5, 1 و4, 2, 8. ينقسم النصف الأول إلى 5 و1، فيُدمجان إلى 1, 5. وينقسم النصف الثاني إلى 4 و2, 8؛ وتُدمج 2, 8 من 2 و8، ثم تُدمج مع 4 إلى 2, 4, 8. وأخيرًا تُدمج 1, 5 و2, 4, 8: 1، ثم 2، ثم 4، ثم 5، وتبقى 8. أي 8 مقارنات و12 كتابة و4 عمليات دمج.

لماذا n log n

كل تقسيم ينصّف القطع، لذا تصبح كل قطعة قيمة واحدة بعد نحو log₂ n مستوى. وفي طريق العودة، يتعامل كل مستوى من الدمج مع كل قيمة مرة واحدة، أي n كتابة وأقل من n مقارنة في كل مستوى. والمجموع نحو n log₂ n. ولـ 40 قيمة يُجري الترتيب 216 كتابة و177 مقارنة على الأكثر؛ بينما قد يحتاج الترتيب الفقاعي إلى 780 مقارنة للقائمة نفسها. كما أن ترتيب المدخلات أقل تأثيرًا بكثير مما في تلك الخوارزميات: لـ 40 قيمة، تحتاج القائمة المرتبة إلى 100 مقارنة، والمعكوسة إلى 116، والعشوائية إلى نحو 160.

المخزن المؤقت والاستقرار

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

التاريخ والاستخدام

وصف John von Neumann الترتيب بالدمج عام 1945، مما يجعله من أوائل الخوارزميات المكتوبة لحاسوب ذي برنامج مخزَّن. ولأنه يقرأ البيانات ويكتبها في مقاطع طويلة متتالية، كان الطريقة المعيارية لترتيب البيانات على الأشرطة، ولا يزال يُستخدم للملفات الأكبر من أن تتسع لها الذاكرة. وTimsort، الذي تستخدمه Python وتستخدمه Java للكائنات، هو ترتيب بالدمج يبحث أولًا عن المقاطع المرتبة أصلًا ويستخدم الترتيب بالإدراج للقطع القصيرة.

جون فون نيومان في صورة شارته في لوس ألاموس. وصف فرز الدمج عام 1945، وهو من أوائل الخوارزميات المكتوبة لحاسوب ذي برنامج مخزّن.
جون فون نيومان في صورة شارته في لوس ألاموس. وصف فرز الدمج عام 1945، وهو من أوائل الخوارزميات المكتوبة لحاسوب ذي برنامج مخزّن.

استكشفه

افتح التطبيق واضغط خطوة. الجزء المظلل من القائمة هو ما يجري تقسيمه أو دمجه، والخط المتقطع يحدد المنتصف. عندما يبدأ الدمج، ينزل النصفان إلى صف المخزن المؤقت؛ وتُقارن القيمتان الأوليان، وتصعد الأصغر عائدةً. راقب العدادات: الكتابات متساوية لكل قائمة بالطول نفسه، والمقارنات أقل ما تكون لقائمة مرتبة أو معكوسة وأكثر ما تكون لقائمة عشوائية، لكنها لا تتجاوز نحو n log₂ n.

الأسئلة المتداولة

ما التعقيد الزمني للترتيب بالدمج؟

O(n log n) في أفضل الحالات ومتوسطها وأسوئها. وتحتاج النسخة المعتادة إلى ذاكرة إضافية O(n) للمخزن المؤقت.

ما الفرق بين الترتيب بالدمج والترتيب السريع؟

كلاهما يقسم القائمة ويرتب الأجزاء. يقسم الترتيب بالدمج عند المنتصف دون النظر إلى القيم ويؤدي عمله عند الدمج؛ أما الترتيب السريع فيؤدي عمله عند التقسيم، بنقل القيم حول محور، ولا يحتاج إلى دمج. يرتب الترتيب السريع في المكان وغالبًا ما يكون أسرع عمليًا، لكنه قد يتباطأ إلى n² مع المدخلات السيئة وليس مستقرًا. أما الترتيب بالدمج فهو دائمًا n log n ومستقر.

ما الترتيب بالدمج من الأسفل إلى الأعلى؟

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

هل الترتيب بالدمج مستقر؟

نعم، ما دام التساوي يأخذ القيمة من النصف الأول أولًا، كما يفعل هذا التطبيق.

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

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