يشبه فرز الدمج خوارزمية الفرز السريع حيث يعمل على مفهوم فرق تسد. إنها واحدة من خوارزميات الفرز الأكثر شعبية وكفاءة. إنه أفضل مثال على فئة خوارزميات فرق تسد.

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

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

دمج مفهوم الفرز

دعونا نرى الرسم البياني التالي لفرز الدمج.

لقد قسمنا القائمة المعطاة إلى نصفين. لا يمكن تقسيم القائمة إلى أجزاء متساوية، فلا يهم على الإطلاق.

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

يوفر النهج من أسفل إلى أعلى مزيدًا من التحسين الذي سنحدده لاحقًا.

الجزء الرئيسي من الخوارزمية هو كيفية الجمع بين القائمتين الفرعيتين المصنفتين. دعونا ندمج قائمتي الدمج المرتبتين.

• أ : [ 2 ، 4، 7، 8]
• ب : [ 1 ، 3، 11]
• مرتبة : فارغة

أولاً، نلاحظ العنصر الأول في كلتا القائمتين. نجد أن العنصر الأول في B أصغر، لذلك نضيفه إلى قائمتنا التي تم فرزها ونتقدم للأمام في القائمة B.

• أ : [ 2 ، 4، 7، 8]
• ب : [1، 3 ، أحد عشر]
• الترتيب: 1

ننظر الآن إلى الزوج التالي من العناصر 2 و3. 2 أصغر حجمًا، لذا نضيفه إلى القائمة التي تم فرزها وننتقل إلى القائمة.

• أ : [ 2 ، 4، 7، 8]
• ب : [1، 3 ، أحد عشر]
• الترتيب: 1

واصل هذه العملية وننتهي بالقائمة المصنفة {1، 2، 3، 4، 7، 8، 11}. يمكن أن يكون هناك حالتين خاصتين.

نمط تصميم طريقة المصنع

ماذا لو كانت كلتا القائمتين الفرعيتين تحتويان على نفس العناصر - في مثل هذه الحالة، يمكننا نقل أي قائمة فرعية واحدة وإضافة العنصر إلى القائمة التي تم فرزها. من الناحية الفنية، يمكننا المضي قدمًا في كلتا القائمتين الفرعيتين وإضافة العناصر إلى القائمة التي تم فرزها.

لم يبق لدينا أي عنصر في قائمة فرعية واحدة. عندما نفاد القائمة الفرعية، ما عليك سوى إضافة عنصر العنصر الثاني تلو الآخر.

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

تطبيق

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

مصفوفة الفرز

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

 def merge_sort(array, left_index, right_index): if left_index >= right_index: return middle = (left_index + right_index)//2 merge_sort(array, left_index, middle) merge_sort(array, middle + 1, right_index) merge(array, left_index, right_index, middle) 

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

دعونا نفهم الإجراء أعلاه باتباع الخطوات.

ما هو const في جافا

• الخطوة الأولى هي إنشاء نسخ من القوائم. القائمة الأولى تحتوي على القوائم من [يسار_الفهرس،...،وسط] والثاني من [وسط+1،؟،right_index] .
• نقوم باجتياز نسختي القائمة باستخدام المؤشر، واختيار القيمة الأصغر من القيمتين وإضافتهما إلى القائمة التي تم فرزها. بمجرد إضافة العنصر إلى القائمة والمضي قدمًا في القائمة التي تم فرزها بغض النظر.
• أضف العناصر المتبقية في النسخة الأخرى إلى المصفوفة التي تم فرزها.

دعونا ننفذ عملية الدمج في برنامج بايثون.

برنامج بايثون

 # Here, we are declaring the function to divide the lists in to the two sub lists # Here, we are passing the list1, left index, right index as the parameters def merge_sort(list1, left_index, right_index): if left_index &gt;= right_index: # here, we are checking the if condition return middle = (left_index + right_index)//2 # Here, we are finding the middle of the given two numbers merge_sort(list1, left_index, middle) # Here, we are calling the merge sort function till the middle number we got merge_sort(list1, middle + 1, right_index) # Here, we are calling the merge sort function till the end of the list i.e., right index merge(list1, left_index, right_index, middle) # Here, we are calling the merge function to merge the divided list using the merge # sort function above # Here, we are defining a function for merge the list after dividing def merge(list1, left_index, right_index, middle): # Here, we are creating subparts of a lists left_sublist = list1[left_index:middle + 1] right_sublist = list1[middle+1:right_index+1] # Here, we are initializing the values for variables that we use to keep # track of where we are in each list1 left_sublist_index = 0 right_sublist_index = 0 sorted_index = left_index # Here, we are traversing the both copies until we get run out one element while left_sublist_index <len(left_sublist) 1 and right_sublist_index < len(right_sublist): # here, we are declaring a while loop if our left_sublist has the smaller element, put it in sorted part then move forward (by increasing pointer) left_sublist[left_sublist_index] checking condition, is true will enter block list1[sorted_index]="left_sublist[left_sublist_index]" left_sublist_index="left_sublist_index" + otherwise add into right sublist else: moving sorted_index="sorted_index" go through remaining elements them len(left_sublist): len(right_sublist):# list1="[44," 65, 2, 3, 58, 14, 57, 23, 10, 1, 7, 74, 48] print('the given list before performing merge sort is: ', list1) this input unsorted array by user merge_sort(list1, 0, len(list1) -1) after is:', printing amd functions pre> <p> <strong>Output:</strong> </p> <pre> The given list before performing the merge sort is: [44, 65, 2, 3, 58, 14, 57, 23, 10, 1, 7, 74, 48] The given list after performing the merge sort is: [1, 2, 3, 7, 10, 14, 23, 44, 48, 57, 58, 65, 74] </pre> <h2>Sorting Custom Objects</h2> <p>We can also sort the custom objects by using the <a href="/python-tutorial-python-programming-language">Python</a> class. This algorithm is almost similar to the above but we need to make it more versatile and pass the comparison function.</p> <p>We will create a custom class, Car and add a few fields to it. We make few changes in the below algorithm to make it more versatile. We can do this by using the lambda functions.</p> <p>Let&apos;s understand the following example.</p> <h3>Python Program</h3> <pre> class Car: # here, we are declaring a class named car def __init__(self, make, model, year): self.make = make # Here, we are using the self to declare the make variables locally self.model = model # Here, we are using the self to declare the model variables locally self.year = year # Here, we are using the self to declare the year variables locally def __str__(self): return str.format(&apos;Make: {}, Model: {}, Year: {}&apos;, self.make, self.model, self.year) # Here, we are returning the format of the strings given def merge(list1, l, r, m, comp_fun): # Here, we are defining a function for merge the list using the compound function left_copy = list1[l:m + 1] # here, we are coping the left part of the list r_sublist = list1[m+1:r+1] # here, we are coping the right part of the list left_copy_index = 0 # here, we are coping the left part indexes of the list r_sublist_index = 0 # here, we are coping the right part indexes of the list sorted_index = l while left_copy_index <len(left_copy) 1 and r_sublist_index < len(r_sublist): # here, we are declaring a while loop using the comp_fun instead of simple comparison operator if comp_fun(left_copy[left_copy_index], r_sublist[r_sublist_index]): checking condition, it is true then will enter block list1[sorted_index]="left_copy[left_copy_index]" left_copy_index="left_copy_index" + else: condition false else sorted_index="sorted_index" len(left_copy): <len(r_sublist): def merge_sort(list1, l, r, comp_fun): merge sort function to given list l>= r: # Here, we are checking the if condition, if it is true then we will enter the block return m = (l + r)//2 # here, we are finding the middle element of the list merge_sort(list1, l, m, comp_fun) # Here, we are calling the merge sort function till the middle number we got merge_sort(list1, m + 1, r, comp_fun) # Here, we are calling the merge sort function from the middle number we got merge(list1, l, r, m, comp_fun) # Here, we are calling the merge function to merge the divided list using the merge # sort function above car1 = Car(&apos;Renault&apos;, &apos;33 Duster&apos;, 2001) car2 = Car(&apos;Maruti&apos;, &apos;Maruti Suzuki Dzire&apos;, 2015) car3 = Car(&apos;Tata motor&apos;, &apos;Jaguar&apos;, 2004) car4 = Car(&apos;Cadillac&apos;, &apos;Seville Sedan&apos;, 1995) list1 = [car1, car2, car3, car4] merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.year <carb.year) print('cars sorted by year:') for car in list1: # here, we are declaring the loop to iterate through list1 print(car) printing all data of and list print() merge_sort(list1, 0, len(list1) -1, lambda cara, carb: cara.make < carb.make) make:') pre> <p> <strong>Output:</strong> </p> <pre> Cars sorted by year: Make: Cadillac, Model: Seville Sedan, Year: 1995 Make: Renault, Model: 33 Duster, Year: 2001 Make: Tata motor, Model: Jaguar, Year: 2004 Make: Maruti, Model: Maruti Suzuki Dzire, Year: 2015 Cars sorted by make: Make: Cadillac, Model: Seville Sedan, Year: 1995 Make: Maruti, Model: Maruti Suzuki Dzire, Year: 2015 Make: Renualt, Model: 33 Duster, Year: 2001 Make: Tata motor, Model: Jaguar, Year: 2004 </pre> <h2>Optimization</h2> <p>We can improve the performance of the merge sort algorithm. First let&apos;s understand the difference between the top-down and bottom-up merge sort. The bottom-up approach sorts the elements of adjacent lists iteratively where the top-down approach breaks down the lists into the two halves.</p> <p>The given list is [10, 4, 2, 12, 1, 3], instead of breaking it down into [10], [4], [2], [12], [1], [3] - we divide into the sub lists which may already sorted: [10, 4], [2], [1, 12], [3] and now are ready to sort them.</p> <p>Merge sort is inefficient algorithm in both time and space for the smaller sub lists. So, insertion sort is more efficient algorithm than the merge sort for the smaller sub lists.</p> <h2>Conclusion</h2> <p>Merge sort is popular and efficient algorithm. It is more efficient algorithm for the large lists. It does not depend on the any unfortunate decisions that lead to bad runtimes.</p> <p>There is one major demerit in the merge sort. It uses the additional memory that is used to store the temporary copies of lists before merging them. However Merge sort is widely used in the software. Its performance is fast and produces the excellent result.</p> <p>We have discussed the merge sort concept in brief and implement it both on simple integer list and on custom objects via a lambda function used for comparison.</p> <hr></carb.year)></len(left_copy)></pre></len(left_sublist)>

فرز الكائنات المخصصة

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

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

دعونا نفهم المثال التالي.

برنامج بايثون

 class Car: # here, we are declaring a class named car def __init__(self, make, model, year): self.make = make # Here, we are using the self to declare the make variables locally self.model = model # Here, we are using the self to declare the model variables locally self.year = year # Here, we are using the self to declare the year variables locally def __str__(self): return str.format(&apos;Make: {}, Model: {}, Year: {}&apos;, self.make, self.model, self.year) # Here, we are returning the format of the strings given def merge(list1, l, r, m, comp_fun): # Here, we are defining a function for merge the list using the compound function left_copy = list1[l:m + 1] # here, we are coping the left part of the list r_sublist = list1[m+1:r+1] # here, we are coping the right part of the list left_copy_index = 0 # here, we are coping the left part indexes of the list r_sublist_index = 0 # here, we are coping the right part indexes of the list sorted_index = l while left_copy_index <len(left_copy) 1 and r_sublist_index < len(r_sublist): # here, we are declaring a while loop using the comp_fun instead of simple comparison operator if comp_fun(left_copy[left_copy_index], r_sublist[r_sublist_index]): checking condition, it is true then will enter block list1[sorted_index]="left_copy[left_copy_index]" left_copy_index="left_copy_index" + else: condition false else sorted_index="sorted_index" len(left_copy): <len(r_sublist): def merge_sort(list1, l, r, comp_fun): merge sort function to given list l>= r: # Here, we are checking the if condition, if it is true then we will enter the block return m = (l + r)//2 # here, we are finding the middle element of the list merge_sort(list1, l, m, comp_fun) # Here, we are calling the merge sort function till the middle number we got merge_sort(list1, m + 1, r, comp_fun) # Here, we are calling the merge sort function from the middle number we got merge(list1, l, r, m, comp_fun) # Here, we are calling the merge function to merge the divided list using the merge # sort function above car1 = Car(&apos;Renault&apos;, &apos;33 Duster&apos;, 2001) car2 = Car(&apos;Maruti&apos;, &apos;Maruti Suzuki Dzire&apos;, 2015) car3 = Car(&apos;Tata motor&apos;, &apos;Jaguar&apos;, 2004) car4 = Car(&apos;Cadillac&apos;, &apos;Seville Sedan&apos;, 1995) list1 = [car1, car2, car3, car4] merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.year <carb.year) print(\'cars sorted by year:\') for car in list1: # here, we are declaring the loop to iterate through list1 print(car) printing all data of and list print() merge_sort(list1, 0, len(list1) -1, lambda cara, carb: cara.make < carb.make) make:\') pre> <p> <strong>Output:</strong> </p> <pre> Cars sorted by year: Make: Cadillac, Model: Seville Sedan, Year: 1995 Make: Renault, Model: 33 Duster, Year: 2001 Make: Tata motor, Model: Jaguar, Year: 2004 Make: Maruti, Model: Maruti Suzuki Dzire, Year: 2015 Cars sorted by make: Make: Cadillac, Model: Seville Sedan, Year: 1995 Make: Maruti, Model: Maruti Suzuki Dzire, Year: 2015 Make: Renualt, Model: 33 Duster, Year: 2001 Make: Tata motor, Model: Jaguar, Year: 2004 </pre> <h2>Optimization</h2> <p>We can improve the performance of the merge sort algorithm. First let&apos;s understand the difference between the top-down and bottom-up merge sort. The bottom-up approach sorts the elements of adjacent lists iteratively where the top-down approach breaks down the lists into the two halves.</p> <p>The given list is [10, 4, 2, 12, 1, 3], instead of breaking it down into [10], [4], [2], [12], [1], [3] - we divide into the sub lists which may already sorted: [10, 4], [2], [1, 12], [3] and now are ready to sort them.</p> <p>Merge sort is inefficient algorithm in both time and space for the smaller sub lists. So, insertion sort is more efficient algorithm than the merge sort for the smaller sub lists.</p> <h2>Conclusion</h2> <p>Merge sort is popular and efficient algorithm. It is more efficient algorithm for the large lists. It does not depend on the any unfortunate decisions that lead to bad runtimes.</p> <p>There is one major demerit in the merge sort. It uses the additional memory that is used to store the temporary copies of lists before merging them. However Merge sort is widely used in the software. Its performance is fast and produces the excellent result.</p> <p>We have discussed the merge sort concept in brief and implement it both on simple integer list and on custom objects via a lambda function used for comparison.</p> <hr></carb.year)></len(left_copy)>

تحسين

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

القائمة المعطاة هي [10، 4، 2، 12، 1، 3]، بدلاً من تقسيمها إلى [10]، [4]، [2]، [12]، [1]، [3] - نقسم في القوائم الفرعية التي قد تم فرزها بالفعل: [10، 4]، [2]، [1، 12]، [3] والآن أصبحت جاهزة لفرزها.

يعد فرز الدمج خوارزمية غير فعالة في كل من الزمان والمكان للقوائم الفرعية الأصغر. لذلك، يعد فرز الإدراج خوارزمية أكثر كفاءة من فرز الدمج للقوائم الفرعية الأصغر.

خاتمة

يعد فرز الدمج خوارزمية شائعة وفعالة. إنها خوارزمية أكثر كفاءة للقوائم الكبيرة. لا يعتمد الأمر على أي قرارات مؤسفة تؤدي إلى أوقات تشغيل سيئة.

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

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