merge sort c with examples
C ++マージソート手法。
マージソートアルゴリズムは「 分割統治 」戦略では、問題をサブ問題に分割し、それらのサブ問題を個別に解決します。
次に、これらのサブ問題を組み合わせたり、マージして、統合されたソリューションを形成します。
=> ここで人気のあるC ++トレーニングシリーズを読んでください。
学習内容：
文字を文字列に変換する方法c ++
概要概要
マージソートは、次の手順を使用して実行されます。
＃1） ソートされるリストは、中央の要素でリストを分割することにより、同じ長さの2つの配列に分割されます。リスト内の要素の数が0または1の場合、リストはソートされていると見なされます。
＃二） 各サブリストは、マージソートを再帰的に使用して個別にソートされます。
＃3） 次に、ソートされたサブリストが結合またはマージされて、完全なソート済みリストが形成されます。
一般的なアルゴリズム
マージソート手法の一般的な擬似コードを以下に示します。
長さNの配列Arrを宣言します
N = 1の場合、Arrはすでにソートされています
N> 1の場合、
左= 0、右= N-1
真ん中を探す=（左+右）/ 2
merge_sort（Arr、left、middle）=>前半を再帰的にソートする
merge_sort（Arr、middle + 1、right）を呼び出す=>後半を再帰的にソートする
上記の手順で並べ替えられた配列をマージするには、merge（Arr、left、middle、right）を呼び出します。
出口
上記の擬似コードに示されているように、マージソートアルゴリズムでは、配列を半分に分割し、マージソートを使用して各半分を再帰的にソートします。サブ配列が個別にソートされると、2つのサブ配列がマージされて、完全にソートされた配列が形成されます。
マージソートの擬似コード
以下は、マージソート手法の擬似コードです。まず、配列を再帰的に半分に分割するためのプロシージャマージソートがあります。次に、ソートされた小さい配列をマージして完全にソートされた配列を取得するマージルーチンがあります。
procedure mergesort( array,N ) array – list of elements to be sorted N – number of elements in the list begin if ( N == 1 ) return array var array1 as array = a(0) ... a(N/2) var array2 as array = a(N/2+1) ... a(N) array1 = mergesort(array1) array2 = mergesort(array2) return merge( array1, array2 ) end procedure procedure merge(array1, array2 ) array1 – first array array2 – second array begin var c as array while ( a and b have elements ) if ( array1(0) > array2(0) ) add array2 (0) to the end of c remove array2 (0) from array2 else add array1 (0) to the end of c remove array1 (0) from array1 end if end while while ( a has elements ) add a(0) to the end of c remove a(0) from a end while while ( b has elements ) add b(0) to the end of c remove b(0) from b end while return c end procedureここで、例を使用してマージソート手法を説明しましょう。
図
上の図は、以下の表形式で表示できます。
| パス | ソートされていないリスト | 除算 | ソート済みリスト |
|---|---|---|---|
| 1 | {12、23、2、43、51、35、19、4} | {12,23,2,43} {51,35,19,4} | {} |
| 二 | {12,23,2,43} {51,35,19,4} | {12.23} {2.43} {51.35} {19.4} | {} |
| 3 | {12.23} {2.43} {51.35} {19.4} | {12.23} {2.43} {35.51} {4.19} | {12.23} {2.43} {35.51} {4.19} |
| 4 | {12.23} {2.43} {35.51} {4.19} | {2,12,23,43} {4,19,35,51} | {2,12,23,43} {4,19,35,51} |
| 5 | {2,12,23,43} {4,19,35,51} | {2,4,12,19,23,35,43,51} | {2,4,12,19,23,35,43,51} |
| 6 | {} | {} | {2,4,12,19,23,35,43,51} |
上記の表現に示されているように、最初に配列は長さ4の2つのサブ配列に分割されます。各サブ配列はさらに長さ2の2つのサブ配列に分割されます。次に各サブ配列はさらにサブ配列に分割されます。それぞれ1つの要素の。このプロセス全体が「除算」プロセスです。
配列をそれぞれ単一要素のサブ配列に分割したら、これらの配列をソートされた順序でマージする必要があります。
上の図に示すように、単一の要素の各サブ配列を検討し、最初に要素を組み合わせて、ソートされた順序で2つの要素のサブ配列を形成します。次に、長さ2のソートされたサブ配列がソートされ、結合されて、それぞれ長さが4の2つのサブ配列が形成されます。次に、これら2つのサブ配列を組み合わせて、完全にソートされた配列を形成します。
反復マージソート
上で見たマージソートのアルゴリズムまたは手法は、再帰を使用します。 「 再帰的マージソート 」。
再帰関数は、関数呼び出しスタックを使用して、呼び出し関数の中間状態を格納することがわかっています。また、パラメータなどのその他の簿記情報を格納し、関数の呼び出しのアクティブ化レコードの格納と実行の再開に関してオーバーヘッドを発生させます。
再帰関数の代わりに反復関数を使用すると、これらすべてのオーバーヘッドを取り除くことができます。上記のマージソートアルゴリズムは、ループと意思決定を使用して反復ステップに簡単に変換することもできます。
再帰的マージソートと同様に、反復マージソートもO（nlogn）の複雑さを持っているため、パフォーマンス的には、互いに同等のパフォーマンスを発揮します。単にオーバーヘッドを下げることができます。
このチュートリアルでは、再帰的マージソートに重点を置いており、次に、C ++およびJava言語を使用して再帰的マージソートを実装します。
以下に示すのは、C ++を使用したマージソート手法の実装です。
#include using namespace std; void merge(int *,int, int , int ); void merge_sort(int *arr, int low, int high) { int mid; if (low num; cout<<'Enter '<myarray(i); } merge_sort(myarray, 0, num-1); cout<<'Sorted array
'; for (int i = 0; i < num; i++) { cout< 出力：
ソートする要素の数を入力してください：10
並べ替える要素を10個入力してください：101 10 2 43 12 54 34 64 89 76
ソートされた配列
2 10 12 34 43 54 64 76 89101
このプログラムでは、2つの関数を定義しました。 merge_sort そして 行く 。 merge_sort関数では、配列を2つの等しい配列に分割し、これらのサブ配列のそれぞれでマージ関数を呼び出します。マージ関数では、これらのサブ配列に対して実際の並べ替えを行い、それらを1つの完全に並べ替えられた配列にマージします。
次に、Java言語でマージソート手法を実装します。
class MergeSort { void merge(int arr(), int beg, int mid, int end) { int left = mid - beg + 1; int right = end - mid; int Left_arr() = new int (left); int Right_arr() = new int (right); for (int i=0; i 出力：
入力配列
101 10 2 43 12 54 34 64 89 76
マージソートを使用してソートされた配列
2 10 12 34 43 54 64 76 89101
Java実装でも、C ++実装で使用したのと同じロジックを使用します。
マージソートはリストをソートする効率的な方法であり、主にリンクリストのソートに使用されます。分割統治法を使用しているため、マージソート手法は、小さい配列でも大きい配列でも同じように効率的に機能します。
マージソートアルゴリズムの複雑さの分析
マージソートを使用してソートを実行するために、最初に配列を2つの等しい半分に分割することがわかっています。これは対数関数である「logn」で表され、実行されるステップ数は最大でlog（n + 1）です。
次に、配列の中央の要素を見つけるために、単一のステップ、つまりO（1）が必要です。
次に、サブ配列をn個の要素の配列にマージするために、O（n）の実行時間がかかります。
したがって、マージソートを実行する合計時間はn（log n + 1）になり、O（n * logn）の時間計算量が得られます。
最悪の場合の時間計算量 O（n * log n） ベストケースの時間計算量 O（n * log n） 平均時間計算量 O（n * log n） スペースの複雑さ オン）
マージソートの時間計算量は、常に配列をサブ配列に分割し、線形時間でサブ配列をマージするため、3つのケース（最悪、最良、平均）すべてで同じです。
マージソートは、ソートされていない配列と常に同じ量のスペースを必要とします。したがって、ソートされるリストが配列である場合、マージソートは非常に大きな配列には使用しないでください。ただし、マージソートは、リンクリストのソートにさらに効果的に使用できます。
結論
マージソートは、配列またはリストを多数のサブ配列に分割し、それらを個別にソートしてから、完全にソートされた配列にマージする「分割統治」戦略を使用します。
マージソートは、他のソート方法よりも高速に実行され、同様に小さい配列でも大きい配列でも効率的に機能します。
クイックソートについては、次のチュートリアルで詳しく説明します。
=> ここで初心者向けC ++トレーニングガイドに注意してください。
推奨読書