Šajā rakstā mēs apspriedīsim sapludināšanas kārtošanas algoritmu. Sapludinātā kārtošana ir šķirošanas tehnika, kas seko sadali un valdi pieejai. Šis raksts būs ļoti noderīgs un interesants studentiem, jo viņi eksāmenos var saskarties ar sapludināšanas jautājumu. Programmatūras inženieru kodēšanas vai tehniskajās intervijās plaši tiek uzdoti šķirošanas algoritmi. Tāpēc ir svarīgi apspriest tēmu.
Sapludināšanas kārtošana ir līdzīga ātrās kārtošanas algoritmam, jo tajā elementu kārtošanai tiek izmantota sadalīšanas un iekarošanas pieeja. Tas ir viens no populārākajiem un efektīvākajiem šķirošanas algoritmiem. Tas sadala doto sarakstu divās vienādās daļās, izsauc sevi par divām daļām un pēc tam apvieno abas sakārtotās daļas. Mums ir jādefinē sapludināt () funkciju, lai veiktu apvienošanu.
java scan.nextstring
Apakšsaraksti atkal un atkal tiek sadalīti uz pusēm, līdz sarakstu vairs nevar sadalīt. Pēc tam mēs apvienojam viena elementa sarakstu pāri divu elementu sarakstos, tos sakārtojot. Sakārtotie divu elementu pāri tiek sapludināti četru elementu sarakstos un tā tālāk, līdz iegūstam sakārtoto sarakstu.
Tagad apskatīsim sapludināšanas kārtošanas algoritmu.
Algoritms
Tālāk norādītajā algoritmā arr ir dotais masīvs, ubagot ir sākuma elements un beigas ir pēdējais masīva elements.
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> Izvade:
regresijas testēšana programmatūras testēšanā
Tātad, tas viss par rakstu. Cerams, ka raksts jums būs noderīgs un informatīvs.
Šis raksts neaprobežojās tikai ar algoritmu. Mēs arī apspriedām sapludināšanas kārtošanas sarežģītību, darbību un ieviešanu dažādās programmēšanas valodās.