Javaでのマージソートのプログラム

Java のマージ ソート プログラムは、最も広く使用されている効率的なアルゴリズムの 1 つです。マージ ソートは、特定の問題を複数のサブ問題に分割し、各サブ問題を個別に解決する分割統治手法に基づいています。部分問題が解決されたら、その結果を組み合わせて問題の最終的な解決策を導き出します。マージ ソート アルゴリズムは、主な問題ではなく副問題の処理を伴うため、再帰を使用して実装できます。

マージソートはどのように機能しますか?

マージソートアルゴリズムを使用してソートする必要がある、ソートされていない配列を考えてみましょう。値 18、8、4、13、10、12、7、および 11 で配列をソートする手順は次のとおりです。

無料ソフトウェア開発コースを始めましょう

Web 開発、プログラミング言語、ソフトウェア テスト、その他

• 最初のステップでは、入力配列がサブ配列に分割されるピボット要素を見つけることが含まれます。
• 要素 13 がピボットとして選択されたと考えてみましょう。したがって、元の配列は 2 つのサブ配列に分割されます。最初の部分配列には 18、8、4、13 が含まれ、2 番目の部分配列には残りの要素 10、12、7、11 が含まれます。
• ステップ 2 で取得したサブ配列は、ステップ 1 と同様にさらに細分化され、これが継続されます。
• メイン配列が単一の要素を含むサブ配列に分割されたら、マージされた要素がソート順になるように、これらのサブ配列のマージを再度開始します。
• 実際の分割統治がどのように機能するかは次のとおりです:

Java でのマージソートのプログラム

これは、Java でのマージ ソートの実装を示すコード例です。

コード:

package com.edubca.sorting;
public class MergeSort {
private int[] array;
private int[] tempMergedArr;
private int length;
public static void main(String a[]){
int[] inputArr = {18, 8, 4, 13, 10, 12, 7, 11};
MergeSort mergeSort = new MergeSort();
mergeSort.sort(inputArr);
for(int i:inputArr){
System.out.print(i + " ");
}
}
public void sort(int inputArr[]) {
this.array = inputArr;
this.length = inputArr.length;
this.tempMergedArr = new int[length];
performMergeSort(0, length - 1);
}
private void performMergeSort(int lowerIndex, int higherIndex) {
if (lowerIndex < higherIndex) {
int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
// Sort the left side of the array call performMergeSort recursively
performMergeSort(lowerIndex, middle);
// Sort the right side of the array call performMergeSort recursively
performMergeSort(middle + 1, higherIndex);
// Merge subparts using a temporary array
mergeData(lowerIndex, middle, higherIndex);
}
}
private void mergeData (int lowerIndex, int middle, int higherIndex) {
for (int i = lowerIndex; i <= higherIndex; i++) {
tempMergedArr[i] = array[i];
}
int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex) {
if (tempMergedArr[i] <= tempMergedArr[j]) {
array[k] = tempMergedArr[i];
i++;
} else {
array[k] = tempMergedArr[j];
j++;
}
k++;
}
while (i <= middle) {
array[k] = tempMergedArr[i];
k++;
i++;
}
}
}

上記のコードは、出力としてソートされた配列を生成します。

出力:

マージソートはどのような場合に使用する必要がありますか?

マージソートは次のシナリオで使用できます:

• ソートされるデータ構造がランダム アクセスをサポートしていない場合、マージ ソートは便利で効率的です。
• 高レベルの並列処理が必要な場合は、並列実行される複数のプロセスを使用してさまざまな部分問題を個別に解決できるため、マージ ソートを使用できます。
• リンクされたリストを操作する場合、リストの結合中にポインタを簡単に変更できるため、マージソートがより速くなります。
• マージ ソートは安定したソートと考えることができます。これは、配列内の同じ要素が互いに対して元の位置を維持することを意味します。高い安定性が必要な場合は、マージソートを使用できます。

マージソートの複雑さの分析

マージソートの複雑さの分析ポイントを以下に示します:

• マージ ソートは再帰的アルゴリズムであり、マージ ソートは配列を 2 つの等しい半分に分割し、それらをマージするのに線形時間がかかるため、3 つのケース (最悪、最良、平均) のすべてで時間計算量は O(n*log n) です。 .
• マージ ソートは再帰的アプローチで動作するため、空間複雑度は O (n) です。したがって、マージ ソートは、高速、スペース、時間効率の良いアルゴリズムと考えることができます。

マージソートと他のアルゴリズムの比較

以下の点は、マージソートと他のアルゴリズムを比較します:

• ヒープ ソートの時間計算量はマージ ソートと同じですが、必要な補助スペースはマージ ソートの O (n) ではなく O (1) のみです。したがって、ヒープ ソートはマージ ソートよりもスペース効率が高くなります。
• クイック ソートの実装は、通常、RAM ベースの配列を並べ替えるマージ ソートよりも優れたパフォーマンスを発揮します。
• リンク リストを使用する場合、ポインタは簡単に変更できるため、マージ ソートはクイック ソートおよびヒープ ソート アルゴリズムよりも優れたパフォーマンスを発揮します。

結論 - Java でのマージ ソートのプログラム

この記事では、マージ ソートはアルゴリズムに関して理解する必要がある重要な概念であると結論付けています。

以上がJavaでのマージソートのプログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。