merge sort java program implement mergesort
このチュートリアルでは、Javaでのマージソート、MergeSortアルゴリズム、擬似コード、マージソートの実装、反復および再帰的なMergeSortの例について説明します。
マージソート手法は、「分割統治」戦略を使用します。この手法では、ソートされるデータセットを小さな単位に分割してソートします。
=> EasyJavaトレーニングシリーズをお読みください。
学習内容：
Javaでのマージソート
例えば、 配列がmergesortを使用してソートされる場合、配列はその中央の要素の周りで2つのサブ配列に分割されます。これらの2つのサブ配列は、ユニットごとに1つの要素しかなくなるまで、さらに小さなユニットに分割されます。
除算が完了すると、この手法では、各要素を比較し、マージ時にそれらを並べ替えることによって、これらの個々のユニットをマージします。このようにして、配列全体がマージされて戻るまでに、ソートされた配列が取得されます。
このチュートリアルでは、アルゴリズムと擬似コード、およびJavaでの手法の実装を含む、このソート手法の一般的な詳細について説明します。
JavaでのMergeSortアルゴリズム
以下は、この手法のアルゴリズムです。
＃1） 長さNの配列myArrayを宣言します
＃二） N = 1かどうかを確認し、myArrayはすでにソートされています
＃3） Nが1より大きい場合
- 左= 0、右= N-1に設定
- 真ん中を計算=（左+右）/ 2
- サブルーチンmerge_sort（myArray、left、middle）を呼び出す=>これは配列の前半をソートします
- サブルーチンmerge_sort（myArray、middle + 1、right）を呼び出す=>これは配列の後半をソートします
- サブルーチンmerge（myArray、left、middle、right）を呼び出して、上記の手順でソートされた配列をマージします。
＃4） 出口
アルゴリズムの手順に見られるように、配列は中央で2つに分割されています。次に、配列の左半分を再帰的にソートしてから、右半分をソートします。両方の半分を個別に並べ替えると、それらがマージされて、並べ替えられた配列が取得されます。
マージソート擬似コード
マージソート手法の擬似コードを見てみましょう。これは「分割統治」手法であるため、すでに説明したように、データセットを分割してから、並べ替えられたデータセットをマージするためのルーチンを示します。
procedure mergesort( var intarray as array ) if ( n == 1 ) return intarray var lArray as array = intarray(0) ... intarray (n/2) var rArray as array = intarray (n/2+1) ... intarray (n) lArray = mergesort(lArray ) rArray = mergesort(rArray ) return merge(lArray, rArray ) end procedure procedure merge( var l_array as array, var r_array as array ) var result as array while (l_array and r_array have elements ) if (l_array (0) > r_array (0) ) add r_array (0) to the end of result remove r_array (0) from r_array else add l_array (0) to the end of result remove l_array (0) from l_array end if end while while (l_array has elements ) add l_array (0) to the end of result remove l_array (0) from l_array end while while (r_array has elements ) add r_array (0) to the end of result remove r_array (0) from r_array end while return result end procedure上記の擬似コードには、マージソートとマージという2つのルーチンがあります。ルーチンMergesortは、入力配列を、並べ替えが簡単な個々の配列に分割します。次に、マージルーチンを呼び出します。
マージルーチンは、個々のサブ配列をマージし、結果のソートされた配列を返します。マージソートのアルゴリズムと擬似コードを見てきましたが、例を使用してこの手法を説明しましょう。
マージソートの図
この手法を使用してソートされる次の配列について考えてみます。
ここで、マージソートアルゴリズムに従って、この配列をその中間要素で2つのサブ配列に分割します。次に、各配列に1つの要素が含まれるまで、サブ配列をより小さな配列に分割し続けます。
各サブ配列に要素が1つしかない場合は、要素をマージします。マージ中に、要素を比較し、マージされた配列内でそれらが正しいことを確認します。そこで、ソートされたマージされた配列を取得するために作業を進めます。
プロセスを以下に示します。
上の図に示すように、配列が繰り返し分割されてからマージされて、ソートされた配列が取得されていることがわかります。この概念を念頭に置いて、Javaプログラミング言語でのマージソートの実装に移りましょう。
Javaでのマージソートの実装
2つのアプローチを使用して、Javaでこの手法を実装できます。
反復マージソート
これはボトムアップアプローチです。それぞれ1つの要素のサブ配列がソートおよびマージされて、2要素の配列が形成されます。次に、これらの配列がマージされて、4要素の配列などが形成されます。このように、ソートされた配列は上に移動することによって構築されます。
以下のJavaの例は、反復的なマージソート手法を示しています。
import java.util.Arrays; class Main { // merge arrays : intArray(start...mid) and intArray(mid+1...end) public static void merge(int() intArray, int() temp, int start, int mid, int end) { int k = start, i = start, j = mid + 1; // traverse through elements of left and right arrays while (i <= mid && j <= end) { if (intArray(i) < intArray(j)) { temp(k++) = intArray(i++); } else { temp(k++) = intArray(j++); } } // Copy remaining elements while (i <= mid) { temp(k++) = intArray(i++); } // copy temp array back to the original array to reflect sorted order for (i = start; i <= end; i++) { intArray(i) = temp(i); } } // sorting intArray(low...high) using iterative approach public static void mergeSort(int() intArray) { int low = 0; int high = intArray.length - 1; // sort array intArray() using temporary array temp int() temp = Arrays.copyOf(intArray, intArray.length); // divide the array into blocks of size m // m = (1, 2, 4, 8, 16...) for (int m = 1; m <= high - low; m = 2*m) { for (int i = low; i < high; i += 2*m) { int start = i; int mid = i + m - 1; int end = Integer.min(i + 2 * m - 1, high); //call merge routine to merge the arrays merge(intArray, temp, start, mid, end); } } } public static void main(String() args) { //define array to be sorted int() intArray = { 10,23,-11,54,2,9,-10,45 }; //print the original array System.out.println('Original Array : ' + Arrays.toString(intArray)); //call mergeSort routine mergeSort(intArray); //print the sorted array System.out.println('Sorted Array : ' + Arrays.toString(intArray)); } }出力：
元の配列：(10、23、-11、54、2、9、-10、45)
ソートされた配列：(-11、-10、2、9、10、23、45、54)
再帰的マージソート
これはトップダウンのアプローチです。このアプローチでは、ソートされる配列は、各配列に1つの要素のみが含まれるまで、より小さな配列に分割されます。そうすれば、ソートの実装が簡単になります。
次のJavaコードは、マージソート手法の再帰的アプローチを実装しています。
import java.util.Arrays; public class Main { public static void merge_Sort(int() numArray) { //return if array is empty if(numArray == null) { return; } if(numArray.length > 1) { int mid = numArray.length / 2; //find mid of the array // left half of the array int() left = new int(mid); for(int i = 0; i 出力：
元の配列：(10、23、-11、54、2、9、-10、45)
ソートされた配列：(-11、-10、2、9、10、23、45、54)
次のセクションでは、配列から切り替えて、この手法を使用してリンクリストと配列リストのデータ構造を並べ替えましょう。
Javaでマージソートを使用してリンクリストをソートする
マージソート手法は、リンクリストのソートに最も適した手法です。他のソート手法は、ほとんどがシーケンシャルアクセスであるため、リンクリストに関してはパフォーマンスが低下します。
次のプログラムは、この手法を使用してリンクリストを並べ替えます。
import java.util.*; // A singly linked list node class Node { int data; Node next; Node(int data, Node next) { this.data = data; this.next = next; } }; class Main { //two sorted linked list are merged together to form one sorted linked list public static Node Sorted_MergeSort(Node node1, Node node2) { //return other list if one is null if (node1 == null) return node2; else if (node2 == null) return node1; Node result; // Pick either node1 or node2, and recur if (node1.data <= node2.data) { result = node1; result.next = Sorted_MergeSort(node1.next, node2); } else { result = node2; result.next = Sorted_MergeSort(node1, node2.next); } return result; } //splits the given linked list into two halves public static Node() FrontBackSplit(Node source) { // empty list if (source == null || source.next == null) { return new Node(){ source, null } ; } Node slow_ptr = source; Node fast_ptr = source.next; // Advance 'fast' two nodes, and advance 'slow' one node while (fast_ptr != null) { fast_ptr = fast_ptr.next; if (fast_ptr != null) { slow_ptr = slow_ptr.next; fast_ptr = fast_ptr.next; } } // split the list at slow_ptr just before mid Node() l_list = new Node(){ source, slow_ptr.next }; slow_ptr.next = null; return l_list; } // use Merge sort technique to sort the linked list public static Node Merge_Sort(Node head) { // list is empty or has single node if (head == null || head.next == null) { return head; } // Split head into 'left' and 'right' sublists Node() l_list = FrontBackSplit(head); Node left = l_list(0); Node right = l_list(1); // Recursively sort the sublists left = Merge_Sort(left); right = Merge_Sort(right); // merge the sorted sublists return Sorted_MergeSort(left, right); } // function to print nodes of given linked list public static void printNode(Node head) { Node node_ptr = head; while (node_ptr != null) { System.out.print(node_ptr.data + ' -> '); node_ptr = node_ptr.next; } System.out.println('null'); } public static void main(String() args) { // input linked list int() l_list = { 4,1,6,2,7,3,8 }; Node head = null; for (int key: l_list) { head = new Node(key, head); } //print the original list System.out.println('Original Linked List: '); printNode(head); // sort the list head = Merge_Sort(head); // print the sorted list System.out.println('
Sorted Linked List:'); printNode(head); } } 出力：
元のリンクリスト：
8-> 3-> 7-> 2-> 6-> 1-> 4-> null
ソートされたリンクリスト：
1-> 2-> 3-> 4-> 6-> 7-> 8-> null
.binファイルの再生方法
Javaでマージソートを使用してArrayListをソートする
配列やリンクリストと同様に、この手法を使用してArrayListを並べ替えることもできます。同様のルーチンを使用して、ArrayListを再帰的に分割してから、サブリストをマージします。
以下のJavaコードは、ArrayListのマージソート手法を実装しています。
import java.util.ArrayList; class Main { //splits arrayList into sub lists. public static void merge_Sort(ArrayList numList){ int mid; ArrayList left = new ArrayList<>(); ArrayList right = new ArrayList<>(); if (numList.size() > 1) { mid = numList.size() / 2; // left sublist for (int i = 0; i numList, ArrayList left, ArrayList right){ //temporary arraylist to build the merged list ArrayList temp = new ArrayList<>(); //initial indices for lists int numbersIndex = 0; int leftIndex = 0; int rightIndex = 0; //traverse left and righ lists for merging while (leftIndex = left.size()) { temp = right; tempIndex = rightIndex; } else { temp = left; tempIndex = leftIndex; } for (int i = tempIndex; i numList = new ArrayList<>(); int temp; //populate the ArrayList with random numbers for (int i = 1; i <= 9; i++) numList.add( (int)(Math.random() * 50 + 1) ); //print original ArrayList of random numbers System.out.println('Original ArrayList:'); for(int val: numList) System.out.print(val + ' '); //call merge_Sort routine merge_Sort(numList); //print the sorted ArrayList System.out.println('
Sorted ArrayList:'); for(int ele: numList) System.out.print(ele + ' '); System.out.println(); } } 出力：
元のArrayList：
17 40 36 7 6 23 35 2 38
ソートされたArrayList：
2 6 7 17 23 35 36 38 40
よくある質問
Q＃1）マージソートは再帰なしで実行できますか？
回答： はい。 「反復マージソート」と呼ばれる非再帰的なマージソートを実行できます。これは、単一の要素を持つサブ配列を2つの要素のサブ配列にマージすることから始まるボトムアップアプローチです。
次に、これらの2要素のサブ配列は、反復構造を使用して4要素のサブ配列などにマージされます。このプロセスは、ソートされた配列ができるまで続きます。
Q＃2） マージソートはその場で行うことができますか？
回答： マージソートは通常、インプレースではありません。しかし、巧妙な実装を使用することで、その場でそれを実現できます。 例えば、 1つの位置に2つの要素の値を格納することによって。これは、モジュラスと除算を使用して後で抽出できます。
Q＃3） 3ウェイマージソートとは何ですか？
回答： 上で見た手法は、配列を2つの部分に分割する2方向マージソートです。次に、配列を並べ替えてマージします。
3方向のマージソートでは、配列を2つの部分に分割する代わりに、3つの部分に分割し、並べ替えて、最後にマージします。
Q＃4） マージソートの時間計算量はどれくらいですか？
回答： すべての場合のマージソートの全体的な時間計算量はO（nlogn）です。
Q＃5） マージソートはどこで使用されますか？
回答： これは主に、リンクリストをO（nlogn）時間でソートする際に使用されます。また、ソート前またはソート後に新しいデータがシステムに入力される分散シナリオでも使用されます。これは、さまざまなデータベースシナリオでも使用されます。
結論
マージソートは安定したソートであり、最初にデータセットをサブセットに繰り返し分割し、次にこれらのサブセットをソートおよびマージして、ソートされたデータセットを形成することによって実行されます。データセットは、各データセットが簡単で並べ替えが簡単になるまで分割されます。
ソート手法への再帰的かつ反復的なアプローチを見てきました。また、Mergesortを使用したリンクリストとArrayListデータ構造の並べ替えについても説明しました。
今後のチュートリアルでは、さらに多くの並べ替え手法について説明します。乞うご期待！
=> 独占的なJavaトレーニングチュートリアルシリーズについては、こちらをご覧ください。
推奨読書
