دمج برنامج الفرز في Java: الفرق بين دمج الفرز و Quicksort

مقدمة عن برنامج دمج الفرز في جافا

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

يمكن أن تكون المشاكل الفرعية المكونة إما متشابهة أو مرتبطة إلى حد ما بالمشكلة الرئيسية. يتم بعد ذلك دمج الحلول الفردية لكل مشكلة فرعية للوصول إلى حل المشكلة الأصلية الأصلية.

كيف يعمل برنامج دمج الفرز في جافا؟

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

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

الفرق بين Quicksort و Merge Sort Program في جافا

على الرغم من التشابه الوظيفي ، إلا أنه يجب التركيز على الاختلاف الأساسي بين الترتيب السريع والدمج في جافا.

• الآلية : Quicksort هي خوارزمية فرز داخلية في المكان ، في حين أن mergesort هي خوارزمية فرز خارجية خارج المكان. في التصنيف السريع ، يتم فرز العناصر على أساس عنصر أساسي يعرف باسم المحور. المحور المحوري بشكل عام هو القيمة الوسطى في مصفوفة الإدخال. يتم دفع العناصر ذات القيمة الأقل من المحور إلى الجانب الأيسر للمحور ، بينما يتم دفع العناصر ذات القيمة الأكبر إلى الجانب الأيمن للمحور. هنا ، يُشار إلى الجانب الأيسر بالقسم الأيسر ، ويُشار إلى الجانب الأيمن باسم القسم الأيمن. على العكس من ذلك ، يقسم الترتيب المدمج المصفوفة إلى صفيفتين فرعيتين (n / 2) بشكل متكرر حتى يتم ترك عنصر واحد فقط. ثم يقوم بدمج المصفوفات الفرعية لتكوين المصفوفة التي تم فرزها.
• التطبيق: بينما يعد التصنيف السريع مناسبًا للصفائف الصغيرة ، يعمل الترتيب المدمج مع أي مجموعة ، بغض النظر عن حجمها.
• السرعة : في حالة الفرز السريع ، كلما كانت مجموعة البيانات أصغر ، زادت سرعة الخوارزمية. من ناحية أخرى ، يعمل الترتيب المدمج بسرعة ثابتة لجميع مجموعات البيانات.
• متطلبات المساحة واستخدام الذاكرة: كما ذكرنا سابقًا ، يعد ترتيب الدمج خوارزمية فرز خارجية خارج المكان. تعقيده المكاني هو O (n). لذلك ، يتطلب تخزينًا إضافيًا لـ (O (n)) لفرز الصفيف الإضافي.

اقرأ أيضًا: أنواع الأحرف في Java مع أمثلة

الوقت- تحليل التعقيد لبرنامج دمج الفرز في جافا

برنامج فرز الدمج في JAVA لديه تعقيد زمني لـ O (n * log n). وفقًا للبحث الثنائي ، كلما تم تقسيم رقم إلى نصفين في كل خطوة ، يمكن تمثيله بالدالة اللوغاريتمية 'log n'. يمكن تمثيل عدد الخطوات (على الأكثر) بواسطة log n +1. منتصف أي مجموعة فرعية هو O (1).

وبالتالي ، لدمج المصفوفات الفرعية ، سيكون وقت تشغيل O (n) مطلوبًا. ومن ثم ، فإن الوقت الإجمالي لبرنامج فرز الدمج في JAVA يصبح n (log n +1). يرقى هذا إلى تعقيد زمني لـ O (n * log n) في جميع الحالات الثلاث (الأسوأ والمتوسط ​​والأفضل) حيث يستغرق فرز الدمج دائمًا وقتًا خطيًا لدمج نصفين.

تعلم دورات البرمجيات عبر الإنترنت من أفضل الجامعات في العالم. اربح برامج PG التنفيذية أو برامج الشهادات المتقدمة أو برامج الماجستير لتتبع حياتك المهنية بشكل سريع.

تلخيص لما سبق

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

إذا كنت مهتمًا بمعرفة المزيد حول Java ، تطوير البرامج الكاملة ، فراجع برنامج upGrad & IIIT-B's Executive PG في تطوير البرامج الكامل المكدس المصمم للمهنيين العاملين ويقدم أكثر من 500 ساعة من التدريب الصارم ، 9+ المشاريع ، والمهام ، وحالة خريجي IIIT-B ، ومشاريع التخرج العملية العملية والمساعدة في العمل مع الشركات الكبرى.