- الجزء قيد الدمج
- قيد المقارنة
- أُعيدت كتابته
- ما دُمج حتى الآن
الترتيب بالدمج
الترتيب بالدمج خوارزمية من نوع فرّق تسد. تقسم القائمة إلى نصفين، وترتب كل نصف بالطريقة نفسها، ثم تدمج النصفين المرتبين بأخذ القيمة الأولى الأصغر مرةً بعد مرة. شاهد الأنصاف تنتقل إلى صف المخزن المؤقت ثم تُكتب من جديد بالترتيب، بأي سرعة أو خطوةً واحدة في كل مرة، واحسب المقارنات والكتابات وعمليات الدمج. اضغط تشغيل لمشاهدة الترتيب، أو خطوة ورجوع للتقدم خطوةً واحدة في كل مرة. اسحب شريط الخطوات للانتقال إلى أي موضع. تعرض المربعات عدد المقارنات والكتابات في القائمة وعمليات الدمج. اختر عدد الأعمدة وترتيبها الأولي، أو اكتب أرقامك. عند تحديد اللوحة، تتقدم مفاتيح الأسهم وترجع خطوةً خطوة، ويشغّل مفتاح المسافة الترتيب ويوقفه مؤقتًا، وينقلك مفتاحا Home وEnd إلى البداية والنهاية.
كيف يعمل
- اختر عدد الأعمدة وترتيبها الأولي: عشوائي، أو شبه مرتب، أو معكوس، أو بقيم مختلفة قليلة. أو اكتب أرقامك.
- اضغط تشغيل، أو استخدم خطوة ورجوع للتقدم خطوةً واحدة في كل مرة. اسحب شريط الخطوات للانتقال إلى أي موضع في الترتيب.
- راقب كل عملية دمج: ينزل النصفان المرتبان إلى المخزن المؤقت، وتصعد القيمة الأولى الأصغر عائدةً، واحدةً تلو الأخرى.
كيف يعمل الترتيب بالدمج
القيمة المنفردة مرتبة أصلًا. أما القائمة الأطول، فقسّمها إلى نصفين ورتّب كل نصف بالترتيب بالدمج. ثم ادمجهما: انظر إلى القيمة الأولى في كل نصف، وانقل الأصغر إلى النتيجة، وكرّر حتى يفرغ النصفان. ولأن النصفين مرتبان، تكون النتيجة مرتبة أيضًا.
دائمًا n log n
التقسيم إلى نصفين مرةً بعد مرة يعطي نحو log₂ n مستوى، وكل مستوى من الدمج يكتب كل قيمة مرة واحدة، لذا يُجري الترتيب نحو n log₂ n كتابة، ولا تزيد المقارنات على ذلك. وعلى عكس الترتيب الفقاعي والترتيب بالاختيار والترتيب بالإدراج، لا ينمو هذا مع n²، ويقل أثر ترتيب القائمة كثيرًا. الثمن هو مخزن مؤقت بطول القائمة. والترتيب بالدمج مستقر أيضًا، ولهذا هو أساس دوال الترتيب في Python وJava.
الأسئلة المتداولة
كيف يعمل الترتيب بالدمج؟
يقسم القائمة إلى نصفين، ويرتب كل نصف بالترتيب بالدمج، ثم يدمج النصفين المرتبين بأخذ الأصغر من قيمتيهما الأوليين مرةً بعد مرة. القائمة ذات القيمة الواحدة مرتبة أصلًا، لذا يتوقف التقسيم عندها.
كم مقارنة يُجري الترتيب بالدمج؟
لـ n قيمة، نحو n log₂ n − n + 1 مقارنة على الأكثر، ونحو نصف n log₂ n على الأقل. ولـ 40 قيمة يكون الحد الأقصى 177. أما الكتابات في القائمة فعددها ثابت دائمًا لكل n: كتابة واحدة لكل قيمة في كل مستوى من الدمج.
لماذا يحتاج الترتيب بالدمج إلى ذاكرة إضافية؟
دمج نصفين في مكانهما يصعب تنفيذه بسرعة، لذا ينسخ الترتيب بالدمج المعتاد النصفين إلى مخزن مؤقت ثم يكتبهما من جديد بالترتيب. المخزن المؤقت بطول القائمة، وهذا عيبه الرئيسي مقارنةً بالترتيب السريع والترتيب بالكومة.
هل الترتيب بالدمج مستقر؟
نعم. عندما تتساوى القيمتان الأوليان، تذهب أولًا القيمة من النصف الأول، فتحافظ القيم المتساوية على ترتيبها الأصلي.
هل تُرسَل أرقامي إلى أي مكان؟
لا. يعمل الترتيب في متصفحك، وتبقى آخر إعداداتك في التخزين المحلي لهذا المتصفح.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
الانتقال إلى المحرر