임의의 배열에 대한 병합 정렬 방법 추가

Question

임의의 배열을 생성하고 빠른 정렬을 사용하는 코드를 만들었습니다. 그러나 병합 정렬 알고리즘을 사용하여 동일한 작업을 수행해야하지만 어떻게해야할지 모르겠습니다. 또한 배열을 한 종류로 분리 할 수 ​​있도록 메뉴가 있어야합니다. 아무도 내가 어떻게 병합 정렬 방법을 추가 할 수있는 몇 가지 아이디어를 게시 할 수 있습니까?

import java.util.Scanner; 
    import java.util.Random; 
    public class Algo { 

    public static void main(String[] args) { 
    Random gen = new Random(); 
    Scanner scanner = new Scanner(System.in); 
    int[] a = new int[20]; 

    for (int i = 0; i < a.length; i++) 
    a[i] = gen.nextInt(100); 

    System.out.println("1. Quick Sort"); 
    System.out.println("2. Merge Sort"); 
    System.out.println("what number do you want?"); 
    int choice = scanner.nextInt(); 
    if (choice == 1) { 
    System.out.println("Quick sort:"); 
    printArray(a); 
    quickSort(a, 0, a.length - 1); 
    printArray(a); 
    } 
    else 
    { 
    System.out.println("Merge sort:"); 
    printArray(a); 
    //MERGE SORT NEEDED 
    printArray(a); 
    } 


} 

private static void printArray(int[] a){ 
    for (int i : a) 
    System.out.print(i + " "); 
    System.out.println(""); 
} 
private static void quickSort(int a[], int left, int right) 
{ 
    int i = left, j = right; 
    int tmp; 
    int pivot = a[(left + right)/2]; 
    while (i <= j) { 
     while (a[i] < pivot) 
       i++; 
     while (a[j] > pivot) 
       j--; 
     if (i <= j) { 
       tmp = a[i]; 
       a[i] = a[j]; 
       a[j] = tmp; 
       i++; 
       j--; 
    } 
} 
if (left < j) 
    quickSort(a, left, j); 
if (i < right) 
     quickSort(a, i, right); 
} 
private static void printArrays(int[] a, int tmp){ 
System.out.println(); 
for (int x = 0; x < a.length; x++){ 
System.out.print(tmp); 
} 
} 
} 

Answer 1

다음은 mergesort에 대한 Java 구현입니다. 필요에 따라 수정할 수 있습니다.

public class MergeSort 
{ 
public int[] arr; 

public MergeSort(int[] a) 
{ 
    arr = a; 
} 

private void mergeSort(int a, int b) 
{ 
    if(a==b) 
     return; 

    int mid = (a+b)/2; 
    mergeSort(a, mid); 
    mergeSort(mid+1, b); 
    merge(a, mid, mid+1, b); 
} 

public void sort() 
{ 
    mergeSort(0, arr.length-1); 
} 

private void merge(int a, int m1, int m2, int b) 
{ 
    int[] sorted = new int[ b-a+1 ]; 
    int i=0, j=0; 

    while((i<(m1-a+1)) &&(j<(b-m2+1))) 
    { 
     if(arr[ a+i ] < arr[ a+j ]) 
     { 
      sorted[ i+j ] = arr[ a+i ]; 
      i++; 
     } 

     else 
     { 
      sorted[ i+j ] = arr[ a+j ]; 
      j++; 
     } 

    } 

    // copy rest of the remaining array 

    while(i< (m1-a+1)) 
    { 
     sorted[ i+j ] = arr[ a+i ]; 
     i++; 
    } 

    while(j<(b-m2+1)) 
    { 
     sorted[ i+j ] = arr[ a+j ]; 
     j++; 
    } 
    System.arraycopy(sorted, 0, arr, a, b - a + 1); 
} 


}