In dit artikel bespreken we het samenvoegsorteeralgoritme. Samenvoegsortering is de sorteertechniek die de verdeel-en-heers-aanpak volgt. Dit artikel zal zeer nuttig en interessant zijn voor studenten, omdat ze tijdens hun examens te maken kunnen krijgen met samenvoegingsvragen. In codeer- of technische interviews voor software-ingenieurs wordt veel gevraagd naar sorteeralgoritmen. Het is dus belangrijk om het onderwerp te bespreken.
Samenvoegsortering is vergelijkbaar met het snelle sorteeralgoritme, omdat het de verdeel-en-heers-aanpak gebruikt om de elementen te sorteren. Het is een van de meest populaire en efficiënte sorteeralgoritmen. Het verdeelt de gegeven lijst in twee gelijke helften, roept zichzelf op voor de twee helften en voegt vervolgens de twee gesorteerde helften samen. We moeten de samenvoegen() functie om de samenvoeging uit te voeren.
De sublijsten worden keer op keer in twee helften verdeeld totdat de lijst niet verder kan worden verdeeld. Vervolgens combineren we de twee lijsten met één element tot lijsten met twee elementen, waarbij we ze daarbij sorteren. De gesorteerde paren met twee elementen worden samengevoegd in de lijsten met vier elementen, enzovoort totdat we de gesorteerde lijst krijgen.
Laten we nu eens kijken naar het algoritme voor het samenvoegen van sorteringen.
Algoritme
In het volgende algoritme arr is de gegeven array, smeken is het startelement, en einde is het laatste element van de array.
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> Uitgang:
Dus dat is alles over het artikel. Ik hoop dat het artikel nuttig en informatief voor u zal zijn.
Dit artikel beperkte zich niet alleen tot het algoritme. We hebben ook de complexiteit, werking en implementatie van het samenvoegen in verschillende programmeertalen besproken.