logo

マージソートアルゴリズム

この記事では、マージソートアルゴリズムについて説明します。マージ ソートは、分割統治アプローチに従った並べ替え手法です。この記事は、マージ ソートが試験問題として出題される可能性がある学生にとって、非常に役立ち、興味深いものとなるでしょう。ソフトウェア エンジニアのコーディング面接や技術面接では、ソート アルゴリズムについてよく質問されます。したがって、そのテーマについて話し合うことが重要です。

マージ ソートは、分割統治アプローチを使用して要素をソートするため、クイック ソート アルゴリズムに似ています。これは、最も一般的で効率的な並べ替えアルゴリズムの 1 つです。指定されたリストを 2 つの等しい半分に分割し、その 2 つの半分に対して自分自身を呼び出してから、ソートされた 2 つの半分をマージします。を定義する必要があります。 マージ() マージを実行する関数。

int型の文字列

サブリストは、リストがそれ以上分割できなくなるまで、何度も半分に分割されます。次に、1 要素リストのペアを 2 要素リストに結合し、その過程で並べ替えます。ソートされた 2 要素のペアは 4 要素のリストにマージされ、ソートされたリストが得られるまでこれが繰り返されます。

では、マージソートのアルゴリズムを見てみましょう。

アルゴリズム

次のアルゴリズムでは、 到着しました は指定された配列です。 懇願する は開始要素であり、 終わり 配列の最後の要素です。

 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&#x2026;mid]</strong> and <strong>A[mid+1&#x2026;end]</strong> , to build one sorted array <strong>A[beg&#x2026;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&apos;s see the working of merge sort Algorithm.</p> <p>To understand the working of the merge sort algorithm, let&apos;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&apos;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&apos;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>&apos;; printArray($a, $n); mergeSort($a, 0, $n - 1); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </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&apos;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>

出力:

マージソート

それでは、この記事については以上です。この記事があなたにとって有益で有益であることを願っています。

この記事はアルゴリズムだけに限定されたものではありません。また、マージ ソートの複雑さ、動作、さまざまなプログラミング言語での実装についても説明しました。