merge sort java program implement mergesort
이 자습서에서는 Java의 병합 정렬, MergeSort 알고리즘, 의사 코드, 병합 정렬 구현, 반복 및 재귀 MergeSort의 예에 대해 설명합니다.
병합 정렬 기술은 '분할 및 정복'전략을 사용합니다. 이 기술에서는 정렬 할 데이터 세트를 더 작은 단위로 나누어 정렬합니다.
학습 내용 :
Java에서 정렬 병합
예를 들면 mergesort를 사용하여 배열을 정렬해야하는 경우 배열은 중간 요소 주위에서 두 개의 하위 배열로 나뉩니다. 이 두 개의 하위 배열은 단위당 하나의 요소 만 가질 때까지 더 작은 단위로 더 나뉩니다.
분할이 완료되면이 기술은 각 요소를 비교하고 병합 할 때 정렬하여 이러한 개별 단위를 병합합니다. 이렇게하면 전체 배열이 다시 병합 될 때까지 정렬 된 배열이 생성됩니다.
이 튜토리얼에서는 알고리즘 및 의사 코드를 포함하여 일반적으로이 정렬 기술의 모든 세부 사항과 Java 기술 구현에 대해 설명합니다.
Java의 MergeSort 알고리즘
다음은 기술에 대한 알고리즘입니다.
#1) 길이가 N 인 배열 myArray 선언
#두) N = 1인지 확인하고 myArray가 이미 정렬되어 있습니다.
#삼) N이 1보다 크면
- 왼쪽 = 0, 오른쪽 = N-1 설정
- 중간 계산 = (왼쪽 + 오른쪽) / 2
- subroutine merge_sort (myArray, left, middle) 호출 => 배열의 전반부 정렬
- subroutine merge_sort (myArray, middle + 1, right) 호출 => 배열의 후반부를 정렬합니다.
- 서브 루틴 병합 (myArray, left, middle, right)을 호출하여 위 단계에서 정렬 된 배열을 병합합니다.
# 4) 출구
알고리즘 단계에서 볼 수 있듯이 배열은 중간에서 두 개로 나뉩니다. 그런 다음 배열의 왼쪽 절반과 오른쪽 절반을 재귀 적으로 정렬합니다. 두 반쪽을 개별적으로 정렬하면 정렬 된 배열을 얻기 위해 병합됩니다.
정렬 의사 코드 병합
Mergesort 기법에 대한 의사 코드를 살펴 보겠습니다. 이것은 '분할 정복'기법이므로 이미 논의했듯이 데이터 세트를 분할 한 다음 정렬 된 데이터 세트를 병합하는 루틴을 제시합니다.
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위의 의사 코드에는 Mergesort와 merge라는 두 가지 루틴이 있습니다. Mergesort 루틴은 입력 배열을 정렬하기 쉬운 개별 배열로 분할합니다. 그런 다음 병합 루틴을 호출합니다.
병합 루틴은 개별 하위 배열을 병합하고 결과로 정렬 된 배열을 반환합니다. 병합 정렬을위한 알고리즘과 의사 코드를 확인 했으므로 이제 예제를 사용하여이 기술을 설명하겠습니다.
MergeSort 일러스트레이션
이 기술을 사용하여 정렬 할 다음 배열을 고려하십시오.
이제 Merge 정렬 알고리즘에 따라 중간 요소에서이 배열을 두 개의 하위 배열로 분할합니다. 그런 다음 각 배열에서 단일 요소를 얻을 때까지 하위 배열을 더 작은 배열로 계속 분할합니다.
각 하위 배열에 하나의 요소 만 있으면 요소를 병합합니다. 병합하는 동안 요소를 비교하고 병합 된 배열에서 순서대로 있는지 확인합니다. 그래서 우리는 정렬 된 병합 된 배열을 얻기 위해 노력합니다.
프로세스는 다음과 같습니다.
위의 그림에서 볼 수 있듯이 배열이 반복적으로 분할 된 다음 병합되어 정렬 된 배열을 얻는 것을 볼 수 있습니다. 이 개념을 염두에두고 Java 프로그래밍 언어로 Mergesort를 구현해 보겠습니다.
Java에서 정렬 구현 병합
우리는 두 가지 접근 방식을 사용하여 Java로 기술을 구현할 수 있습니다.
반복적 병합 정렬
이것은 상향식 접근 방식입니다. 한 요소의 하위 배열은 각각 정렬 및 병합되어 요소가 두 개인 배열을 형성합니다. 그런 다음 이러한 배열이 병합되어 요소가 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)
재귀 병합 정렬
이것은 하향식 접근 방식입니다. 이 접근 방식에서 정렬 할 배열은 각 배열에 하나의 요소 만 포함될 때까지 더 작은 배열로 나뉩니다. 그러면 정렬이 쉽게 구현됩니다.
다음 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
PC 용 최고의 유튜브 비디오 다운로더
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 요소 하위 배열은 반복 구조를 사용하여 4 요소 하위 배열로 병합됩니다. 이 프로세스는 정렬 된 배열을 가질 때까지 계속됩니다.
질문 # 2) 병합 정렬을 제자리에서 수행 할 수 있습니까?
대답: 병합 정렬은 일반적으로 제자리에 있지 않습니다. 그러나 우리는 현명한 구현을 사용하여 제자리에 만들 수 있습니다. 예를 들면 한 위치에 두 개의 요소 값을 저장합니다. 이것은 나중에 계수와 나눗셈을 사용하여 추출 할 수 있습니다.
질문 # 3) 3 방향 병합 정렬이란 무엇입니까?
대답: 위에서 본 기술은 배열을 두 부분으로 나누는 2-way Merge 정렬입니다. 그런 다음 배열을 정렬하고 병합합니다.
3-way Merge 정렬에서는 배열을 2 개로 분할하는 대신 3 개로 분할 한 다음 정렬하고 마지막으로 병합합니다.
질문 # 4) Mergesort의 시간 복잡성은 무엇입니까?
대답: 모든 경우 병합 정렬의 전체 시간 복잡도는 O (nlogn)입니다.
질문 # 5) 병합 정렬은 어디에 사용됩니까?
대답: 주로 O (nlogn) 시간에 연결된 목록을 정렬하는 데 사용됩니다. 또한 정렬 전 또는 사후 시스템에 새 데이터가 들어오는 분산 시나리오에서도 사용됩니다. 이것은 다양한 데이터베이스 시나리오에서도 사용됩니다.
결론
병합 정렬은 안정적인 정렬이며 먼저 데이터 집합을 반복적으로 하위 집합으로 분할 한 다음 이러한 하위 집합을 정렬 및 병합하여 정렬 된 데이터 집합을 형성하는 방식으로 수행됩니다. 데이터 세트는 각 데이터 세트가 사소하고 쉽게 정렬 될 때까지 분할됩니다.
우리는 정렬 기술에 대한 반복적이고 반복적 인 접근 방식을 보았습니다. 또한 Mergesort를 사용한 Linked List 및 ArrayList 데이터 구조의 정렬에 대해서도 논의했습니다.
다음 튜토리얼에서 더 많은 정렬 기술에 대한 논의를 계속할 것입니다. 계속 지켜봐주세요!
=> 독점적 인 Java 교육 자습서 시리즈를 보려면 여기를 방문하십시오.
추천 도서
