كيف يتم تطبيق Merge Sort في Python؟



إليك برنامج تعليمي بسيط وسهل لتعلم كيفية استخدام Merge Sort ، والتعرف على خوارزميتها وتنفيذها في Python

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

ما هو ترتيب الدمج في بايثون؟

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





نهج فرق تسد

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

إليك تصور لفرز الدمج لمسح الصورة لك

صفيف الإدخال = [3،1،4،1،5،9،2،6،5،4]



دمج الفرز | مدونات Edureka | إدوريكا
الآن ، دعونا ننتقل إلى التنفيذ.

نقل الملفات إلى مثيل windows ec2

تنفيذ دمج الفرز في بايثون

def mergeSort (nlist): print ('Splitting'، nlist) if len (nlist)> 1: mid = len (nlist) // 2 lefthalf = nlist [: mid] righthalf = nlist [mid:] mergeSort (lefthalf) mergeSort (righthalf) أنا = ي = ك = 0 بينما أنا

انتاج:

$ python main.py
('تقسيم' ، [3 ، 1 ، 4 ، 1 ، 5 ، 9 ، 2 ، 6 ، 5 ، 4])
('تقسيم' ، [3 ، 1 ، 4 ، 1 ، 5])
('تقسيم' ، [3 ، 1])
('تقسيم' ، [3])
('دمج' ، [3])
('تقسيم' ، [1])
('دمج' ، [1])
('دمج' ، [1 ، 3])
('تقسيم' ، [4 ، 1 ، 5])
('تقسيم' ، [4])
('دمج' ، [4])
('تقسيم' ، [1 ، 5])
('تقسيم' ، [1])
('دمج' ، [1])
('تقسيم' ، [5])
('دمج' ، [5])
('دمج' ، [1 ، 5])
('دمج' ، [1 ، 4 ، 5])
('دمج' ، [1 ، 1 ، 3 ، 4 ، 5])
('تقسيم' ، [9 ، 2 ، 6 ، 5 ، 4])
('تقسيم' ، [9 ، 2])
('تقسيم' ، [9])
('دمج' ، [9])
('تقسيم'، [2])
('دمج' ، [2])
('دمج' ، [2 ، 9])
('تقسيم' ، [6 ، 5 ، 4])
('تقسيم' ، [6])
('دمج' ، [6])
('تقسيم' ، [5 ، 4])
('تقسيم' ، [5])
('دمج' ، [5])
('تقسيم' ، [4])
('دمج' ، [4])
('دمج' ، [4 ، 5])
('دمج' ، [4 ، 5 ، 6])
('دمج' ، [2 ، 4 ، 5 ، 6 ، 9])
('دمج' ، [1 ، 1 ، 2 ، 3 ، 4 ، 4 ، 5 ، 5 ، 6 ، 9])
[1 ، 1 ، 2 ، 3 ، 4 ، 4 ، 5 ، 5 ، 6 ، 9]



تحليل المشاعر على تويتر باستخدام سبارك

مخطط التدفق لتنفيذ دمج الفرز

مزايا واستخدام فرز الدمج

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

بهذا ، وصلنا إلى نهاية هذه المدونة حول 'كيفية تنفيذ Merge Sort في Python'. آمل أن يضيف المحتوى بعض القيمة إلى معرفتك في بايثون. للحصول على معرفة متعمقة حول Python مع تطبيقاتها المختلفة ، يمكنك التسجيل في البث المباشر مع دعم على مدار الساعة طوال أيام الأسبوع وإمكانية الوصول مدى الحياة.