في هذه المقالة، سنناقش خوارزمية الفرز المدمج. دمج الفرز هو أسلوب الفرز الذي يتبع نهج فرق تسد. ستكون هذه المقالة مفيدة جدًا ومثيرة للاهتمام للطلاب حيث قد يواجهون نوع الدمج كسؤال في امتحاناتهم. في المقابلات التقنية أو الترميزية لمهندسي البرمجيات، يتم طرح خوارزميات الفرز على نطاق واسع. لذلك، من المهم مناقشة الموضوع.
يشبه فرز الدمج خوارزمية الفرز السريع لأنه يستخدم أسلوب فرق تسد لفرز العناصر. إنها واحدة من خوارزميات الفرز الأكثر شعبية وكفاءة. فهو يقسم القائمة المعطاة إلى نصفين متساويين، ويطلق على نفسه اسم النصفين ثم يدمج النصفين المفرزين. علينا أن نحدد دمج() وظيفة لتنفيذ الدمج.
اختصارات لينكس
يتم تقسيم القوائم الفرعية مرارًا وتكرارًا إلى نصفين حتى لا يمكن تقسيم القائمة بشكل أكبر. ثم نقوم بدمج قوائم العناصر المكونة من عنصر واحد في قوائم مكونة من عنصرين، ونقوم بفرزها في هذه العملية. يتم دمج الأزواج المكونة من عنصرين التي تم فرزها في قوائم العناصر الأربعة، وهكذا حتى نحصل على القائمة التي تم فرزها.
الآن، دعونا نرى خوارزمية فرز الدمج.
خوارزمية
في الخوارزمية التالية، وصول هي المصفوفة المعطاة، إفترض جدلا هو عنصر البداية، و نهاية هو العنصر الأخير في المصفوفة.
MERGE_SORT(arr, beg, end) if beg <end 2 set mid="(beg" + end) merge_sort(arr, beg, mid) 1, merge (arr, mid, end of if merge_sort < pre> <p>The important part of the merge sort is the <strong>MERGE</strong> function. This function performs the merging of two sorted sub-arrays that are <strong>A[beg…mid]</strong> and <strong>A[mid+1…end]</strong> , to build one sorted array <strong>A[beg…end]</strong> . So, the inputs of the <strong>MERGE</strong> function are <strong>A[], beg, mid,</strong> and <strong>end</strong> .</p> <p>The implementation of the <strong>MERGE</strong> function is given as follows -</p> <pre> /* Function to merge the subarrays of a[] */ void merge(int a[], int beg, int mid, int end) { int i, j, k; int n1 = mid - beg + 1; int n2 = end - mid; int LeftArray[n1], RightArray[n2]; //temporary arrays /* copy data to temp arrays */ for (int i = 0; i <n1; 1 i++) leftarray[i]="a[beg" + i]; for (int j="0;" < n2; j++) rightarray[j]="a[mid" j]; i="0," * initial index of first sub-array second k="beg;" merged while (i n1 && n2) { if(leftarray[i] a[k]="LeftArray[i];" i++; } else j++; k++; (i<n1) (j<n2) pre> <h2>Working of Merge sort Algorithm</h2> <p>Now, let's see the working of merge sort Algorithm.</p> <p>To understand the working of the merge sort algorithm, let's take an unsorted array. It will be easier to understand the merge sort via an example.</p> <p>Let the elements of array are -</p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm.webp" alt="Merge sort"> <p>According to the merge sort, first divide the given array into two equal halves. Merge sort keeps dividing the list into equal parts until it cannot be further divided.</p> <p>As there are eight elements in the given array, so it is divided into two arrays of size 4.</p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-2.webp" alt="Merge sort"> <p>Now, again divide these two arrays into halves. As they are of size 4, so divide them into new arrays of size 2.</p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-3.webp" alt="Merge sort"> <p>Now, again divide these arrays to get the atomic value that cannot be further divided.</p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-4.webp" alt="Merge sort"> <p>Now, combine them in the same manner they were broken.</p> <p>In combining, first compare the element of each array and then combine them into another array in sorted order.</p> <p>So, first compare 12 and 31, both are in sorted positions. Then compare 25 and 8, and in the list of two values, put 8 first followed by 25. Then compare 32 and 17, sort them and put 17 first followed by 32. After that, compare 40 and 42, and place them sequentially.</p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-5.webp" alt="Merge sort"> <p>In the next iteration of combining, now compare the arrays with two data values and merge them into an array of found values in sorted order.</p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-6.webp" alt="Merge sort"> <p>Now, there is a final merging of the arrays. After the final merging of above arrays, the array will look like -</p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-7.webp" alt="Merge sort"> <p>Now, the array is completely sorted.</p> <h2>Merge sort complexity</h2> <p>Now, let's see the time complexity of merge sort in best case, average case, and in worst case. We will also see the space complexity of the merge sort.</p> <h3>1. Time Complexity</h3> <table class="table"> <tr> <th>Case</th> <th>Time Complexity</th> </tr> <tr> <td> <strong>Best Case</strong> </td> <td>O(n*logn)</td> </tr> <tr> <td> <strong>Average Case</strong> </td> <td>O(n*logn)</td> </tr> <tr> <td> <strong>Worst Case</strong> </td> <td>O(n*logn)</td> </tr> </table> <ul> <tr><td>Best Case Complexity -</td> It occurs when there is no sorting required, i.e. the array is already sorted. The best-case time complexity of merge sort is <strong>O(n*logn)</strong> . </tr><tr><td>Average Case Complexity -</td> It occurs when the array elements are in jumbled order that is not properly ascending and not properly descending. The average case time complexity of merge sort is <strong>O(n*logn)</strong> . </tr><tr><td>Worst Case Complexity -</td> It occurs when the array elements are required to be sorted in reverse order. That means suppose you have to sort the array elements in ascending order, but its elements are in descending order. The worst-case time complexity of merge sort is <strong>O(n*logn)</strong> . </tr></ul> <h3>2. Space Complexity</h3> <table class="table"> <tr> <td> <strong>Space Complexity</strong> </td> <td>O(n)</td> </tr> <tr> <td> <strong>Stable</strong> </td> <td>YES</td> </tr> </table> <ul> <li>The space complexity of merge sort is O(n). It is because, in merge sort, an extra variable is required for swapping.</li> </ul> <h2>Implementation of merge sort</h2> <p>Now, let's see the programs of merge sort in different programming languages.</p> <p> <strong>Program:</strong> Write a program to implement merge sort in C language.</p> <pre> #include /* Function to merge the subarrays of a[] */ void merge(int a[], int beg, int mid, int end) { int i, j, k; int n1 = mid - beg + 1; int n2 = end - mid; int LeftArray[n1], RightArray[n2]; //temporary arrays /* copy data to temp arrays */ for (int i = 0; i <n1; 1 42 i++) leftarray[i]="a[beg" + i]; for (int j="0;" < n2; j++) rightarray[j]="a[mid" j]; i="0;" * initial index of first sub-array second k="beg;" merged while (i n1 && n2) { if(leftarray[i] a[k]="LeftArray[i];" i++; } else j++; k++; (i<n1) (j<n2) void mergesort(int a[], int beg, end) if (beg mid="(beg" 2; mergesort(a, mid); 1, end); merge(a, mid, function to print the array printarray(int n) i; n; printf('%d ', a[i]); printf('
'); main() a[]="{" 12, 31, 25, 8, 32, 17, 40, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting elements are -
'); printarray(a, n); 0, 1); printf('after return 0; pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-8.webp" alt="Merge sort"> <p> <strong>Program:</strong> Write a program to implement merge sort in C++ language.</p> <pre> #include using namespace std; /* Function to merge the subarrays of a[] */ void merge(int a[], int beg, int mid, int end) { int i, j, k; int n1 = mid - beg + 1; int n2 = end - mid; int LeftArray[n1], RightArray[n2]; //temporary arrays /* copy data to temp arrays */ for (int i = 0; i <n1; 1 41 i++) leftarray[i]="a[beg" + i]; for (int j="0;" < n2; j++) rightarray[j]="a[mid" j]; i="0;" * initial index of first sub-array second k="beg;" merged while (i n1 && n2) { if(leftarray[i] a[k]="LeftArray[i];" i++; } else j++; k++; (i<n1) (j<n2) void mergesort(int a[], int beg, end) if (beg mid="(beg" 2; mergesort(a, mid); 1, end); merge(a, mid, function to print the array printarray(int n) i; n; cout< <a[i]<<' '; main() a[]="{" 11, 30, 24, 7, 31, 16, 39, }; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting elements are -
'; printarray(a, n); 0, 1); cout<<'
after return 0; pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-9.webp" alt="Merge sort"> <p> <strong>Program:</strong> Write a program to implement merge sort in Java.</p> <pre> class Merge { /* Function to merge the subarrays of a[] */ void merge(int a[], int beg, int mid, int end) { int i, j, k; int n1 = mid - beg + 1; int n2 = end - mid; /* temporary Arrays */ int LeftArray[] = new int[n1]; int RightArray[] = new int[n2]; /* copy data to temp arrays */ for (i = 0; i <n1; 1 41 i++) leftarray[i]="a[beg" + i]; for (j="0;" j < n2; j++) rightarray[j]="a[mid" j]; i="0;" * initial index of first sub-array second k="beg;" merged while (i n1 && n2) { if(leftarray[i] a[k]="LeftArray[i];" i++; } else j++; k++; (i<n1) (j<n2) void mergesort(int a[], int beg, end) if (beg mid="(beg" 2; mergesort(a, mid); 1, end); merge(a, mid, function to print the array printarray(int n) i; n; system.out.print(a[i] ' '); public static main(string args[]) a[]="{" 11, 30, 24, 7, 31, 16, 39, }; n="a.length;" merge m1="new" merge(); system.out.println('
before sorting elements are - m1.printarray(a, n); m1.mergesort(a, 0, 1); system.out.println('
after system.out.println(''); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-10.webp" alt="Merge sort"> <p> <strong>Program:</strong> Write a program to implement merge sort in C#.</p> <pre> using System; class Merge { /* Function to merge the subarrays of a[] */ static void merge(int[] a, int beg, int mid, int end) { int i, j, k; int n1 = mid - beg + 1; int n2 = end - mid; //temporary arrays int[] LeftArray = new int [n1]; int[] RightArray = new int [n2]; /* copy data to temp arrays */ for (i = 0; i <n1; 1 40 i++) leftarray[i]="a[beg" + i]; for (j="0;" j < n2; j++) rightarray[j]="a[mid" j]; i="0;" * initial index of first sub-array second k="beg;" merged while (i n1 && n2) { if(leftarray[i] a[k]="LeftArray[i];" i++; } else j++; k++; (i<n1) (j<n2) static void mergesort(int[] a, int beg, end) if (beg mid="(beg" 2; mergesort(a, mid); 1, end); merge(a, mid, function to print the array printarray(int[] n) i; n; console.write(a[i] ' '); main() int[] a="{" 10, 29, 23, 6, 30, 15, 38, }; n="a.Length;" console.write('before sorting elements are - printarray(a, n); 0, 1); console.write('
after pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-11.webp" alt="Merge sort"> <p> <strong>Program:</strong> Write a program to implement merge sort in PHP.</p> <pre> <?php /* Function to merge the subarrays of a[] */ function merge(&$a, $beg, $mid, $end) { $n1 = ($mid - $beg) + 1; $n2 = $end - $mid; /* temporary Arrays */ $LeftArray = array($n1); $RightArray = array($n2); /* copy data to temp arrays */ for ($i = 0; $i < $n1; $i++) $LeftArray[$i] = $a[$beg + $i]; for ($j = 0; $j < $n2; $j++) $RightArray[$j] = $a[$mid + 1 + $j]; $i = 0; /* initial index of first sub-array */ $j = 0; /* initial index of second sub-array */ $k = $beg; /* initial index of merged sub-array */ while ($i<$n1 && $j<$n2) { if($LeftArray[$i] <= $RightArray[$j]) { $a[$k] = $LeftArray[$i]; $i++; } else { $a[$k] = $RightArray[$j]; $j++; } $k++; } while ($i<$n1) { $a[$k] = $LeftArray[$i]; $i++; $k++; } while ($j<$n2) { $a[$k] = $RightArray[$j]; $j++; $k++; } } function mergeSort(&$a, $beg, $end) { if ($beg < $end) { $mid = (int)(($beg + $end) / 2); mergeSort($a, $beg, $mid); mergeSort($a, $mid + 1, $end); merge($a, $beg, $mid, $end); } } /* Function to print array elements */ function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 10, 29, 23, 6, 30, 15, 38, 40 ); $n = count($a); echo 'Before sorting array elements are - <br>'; printArray($a, $n); mergeSort($a, 0, $n - 1); echo ' <br> After sorting array elements are - <br>'; printArray($a, $n); ?> </pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-12.webp" alt="Merge sort"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Merge sort complexity, working, and implementation in different programming languages.</p> <hr></n1;></pre></n1;></pre></n1;></pre></n1;></pre></n1;></pre></end> انتاج:
لذلك، هذا كل ما في هذه المادة. نأمل أن تكون المقالة مفيدة وغنية بالمعلومات لك.
لم تقتصر هذه المقالة على الخوارزمية فقط. لقد ناقشنا أيضًا تعقيد نوع الدمج والعمل والتنفيذ بلغات برمجة مختلفة.
خوارزمية لbfs