كيفية تنفيذ دمج الفرز في C ++ مع أمثلة

ستزودك هذه المقالة بمعلومات تفصيلية ومعرفة شاملة عن Merge Sort في C ++ ، وكيف تعمل مع الأمثلة.

ما هو نوع الدمج؟ دمج الفرز عبارة عن خوارزمية فرز قائمة على المقارنة تنتمي إلى فئة فرق تسد. يتم استخدام فرز الدمج لفرز مصفوفة استنادًا إلى استراتيجية تقسيم وقهر والتي سيتم تناولها بإيجاز في هذا المنشور جنبًا إلى جنب مع مفاهيم أخرى مثل الخوارزمية مع مثال. سننظر أيضًا في التعقيد الزمني لنوع الدمج في C ++

سيتم تغطية المؤشرات التالية في هذه المقالة ،





الانتقال مع هذه المقالة حول دمج الفرز في C ++

def __init __ (self) python

خوارزمية فرق تسد

إذا كنت بالفعل على دراية بكيفية عمل التصنيف السريع ، فقد تكون على دراية بإستراتيجية فرق تسد. تتضمن فرق تسد ثلاث خطوات رئيسية. لفهم هذه الخطوات ، دعنا نفكر في مصفوفة مرحبًا [] بها فهرس البداية 'a' ومؤشر النهاية 'n' ومن ثم يمكننا كتابة المصفوفة بالطريقة التالية Hello [a & hellip..n]



قسمة- الخطوة الرئيسية أو الخطوة الأولى في تقسيم تسد هي تقسيم المشكلة المحددة إلى مشاكل فرعية أو أجزاء فرعية. المهم هنا هو أن المشكلات الفرعية يجب أن تكون مماثلة للمشكلة الأصلية وأن تكون أصغر في الحجم. في حالتنا هذه ، سنقسم المصفوفة إلى نصفين [a & hellip.m] [m + 1 & hellip..n] يقع في منتصف الفهرس a و n

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

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



الانتقال مع هذه المقالة حول دمج الفرز في C ++

فهم خوارزمية دمج الفرز مع مثال

في هذه المرحلة ، نعرف الطريقة التي سيتم استخدامها بواسطة فرز الدمج. لذا ، دعنا نفكر في مثال وننتقل عبر كل خطوة من Hello [] لم يتم فرزها إلى مصفوفة مرتبة.
مثال- مرحبًا [10 ، 3 ، 7 ، 1 ، 15 ، 14 ، 9 ، 22]

Merge-sort-in-C++

دمج نوع c ++ مثال

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

1. أولاً ، اعتبرنا المصفوفة Hello [10، 3، 7، 1، 15، 14، 9، 22] في هذه المصفوفة يوجد إجمالي 8 عناصر

2. كما رأينا سابقًا ، يستخدم فرز الدمج أسلوب فرّق تسد لفرز العناصر. وجدنا m الذي يقع في منتصف المصفوفة الخاصة بنا وقسمنا المصفوفة من الوسط حيث m = (a - n) / 2 'a' هو مؤشر العنصر الموجود في أقصى اليسار و n هو مؤشر العنصر الموجود في أقصى اليمين من صفيفنا .

3. بعد التقسيم الأول ، لدينا جزأين يتكون كل منهما من 4 عناصر. دعونا نلقي نظرة على النصف الأول [10 ، 3 ، 7 ، 1].

4. نقسم [10 ، 3 ، 7 ، 1] إلى جزأين [10 ، 3] و [7 ، 1]. بعد ذلك نقسمهم إلى [10] ، [3] ، [7] ، [1]. المزيد من القسمة غير ممكن لأننا لا نستطيع حساب م. تعتبر القائمة التي تحتوي على عنصر واحد دائمًا مرتبة.

5. كيف يتم الدمج؟ هيا نكتشف. تتم مقارنة أول [10] و [3] ودمجهما بترتيب تصاعدي [3 ، 10] بنفس الطريقة التي نحصل عليها [1 ، 7]

6. بعد ذلك نقارن [3 ، 10] و [1 ، 7]. بمجرد المقارنة نقوم بدمجها بترتيب تصاعدي ونحصل على [1 ، 3 ، 7 ، 10].

7. [15 ، 14 ، 9 ، 2] مقسمة أيضًا ومدمجة بطريقة مماثلة لتشكيل [9 ، 14 ، 15 ، 22].

8. في الخطوة الأخيرة ، قمنا بمقارنة ودمج [15 ، 14 ، 9 ، 2] [9 ، 14 ، 15 ، 22] لنحصل على مصفوفة مرتبةأي [1 ، 3 ، 7 ، 9 ، 10 ، 14 ، 15 ، 22].

الانتقال مع هذه المقالة حول دمج الفرز في C ++

الكود الزائف لدمج الفرز

ابدأ إذا ترك

تستدعي الدالة mergeSort () نفسها بشكل متكرر لتقسيم المصفوفة الخاصة بنا حتى تصبح عنصرًا واحدًا وتستخدم الدالة merge () لدمج المصفوفات المرتبة.

الانتقال مع هذه المقالة حول دمج الفرز في C ++

دمج برنامج الفرز في C ++

#include #include # include using namespace std void merge (int a []، int Firstindex، int m، int Lastindex) // يدمج المصفوفات الفرعية التي تم إنشاؤها أثناء تقسيم باطل mergeSort (int a []، int Firstindex، int Lastindex) {if (Firstindexالحجم int مرحبا [الحجم] ، أنا cout<<'Enter the elements of the array one by one:n' for(i=0 i>مرحبًا [i] mergeSort (مرحبًا ، 0 ، الحجم - 1) cout<<'The Sorted List isn' for(i=0 i

انتاج-

الانتقال مع هذه المقالة حول دمج الفرز في C ++

كيف تجد أكبر عدد في مصفوفة جافا

تعقيد الوقت

يعد تعقيد الوقت جانبًا مهمًا يجب مراعاته عندما نتحدث عن الخوارزميات. يعتبر فرز الدمج معقدًا كبيرًا للوقت مقارنة بخوارزميات الفرز الأخرى.

وقت تشغيل أسوأ حالة- O (n log n)
أفضل وقت تشغيل الحالة- O (n log n)
متوسط ​​وقت التشغيل- O (n log n)

بهذا ، وصلنا إلى نهاية مقالة دمج الفرز في C ++. إذا كنت ترغب في معرفة المزيد ، تحقق من بواسطة Edureka ، شركة تعليمية موثوقة عبر الإنترنت. تم تصميم دورة تدريب وإصدار شهادات Java J2EE و SOA من Edureka لتدريبك على مفاهيم Java الأساسية والمتقدمة جنبًا إلى جنب مع العديد من أطر Java مثل Hibernate & Spring.

لديك سؤال لنا؟ يرجى ذكر ذلك في قسم التعليقات في هذه المدونة وسنعاود الاتصال بك في أقرب وقت ممكن.