자바에서 병합 정렬에 문제가

Question

나는 아주 새로운 stackoverflow이고 나는 comparables의 arraylist를 mergesort하는 프로그램을 작성하는 데 도움이 필요합니다. 나는이 코드를 몇 시간 동안 사용해 보았지만 아무 소용이 없었다. 내가 컴퓨터 과학 수업을하고 있기 때문에 프로그램이 올바르게 작동해야하고, 다음 과제는 다른 종류의 효율성을 테스트 할 것을 요구합니다.

병합 방법 :

public static void merge(ArrayList <Comparable> a, int first, int mid, int last){ 
    ArrayList <Comparable> b = new ArrayList(); 
    for(int k = first; k <= last; k++){ 
     b.add(a.get(k)); 
    } 

    System.out.println("b now contains " + b); 
    int middle =b.size() /2; 
    for(int i = first; i <= last; i++){ 
     //System.out.println("mid: " + b.size() /2); 
     //System.out.println("b: " + b); 
     //System.out.println("a: " + a); 
     //System.out.println("i: " + i); 
     if(middle == b.size()){ 
      a.set(i, b.remove(0)); 
      middle--; 
     }else if(middle == 0){ 
      a.set(0, b.remove(0)); 
     }else if(b.get(0).compareTo(b.get(middle)) < 0){ 
      System.out.println("moving " + b.get(0) + " from b[0] to a[" + 
       i + "] because " + b.get(0) + " is less than " + b.get(middle)); 
      a.set(i, b.remove(0)); 
      middle--; 
      System.out.println("b now contains " + b); 
     }else{ 
      System.out.println("moving " + b.get(middle) + " from b[" + 
       b.size() /2 + "] to a[" + i + "] because " + b.get(0) + 
        " is greater than " + b.get(middle)); 
      a.set(i, b.remove(middle)); 
      //middle--; 
      System.out.println("b now contains " + b); 
     } 
    } 

    System.out.println(); 
    System.out.println("Merge"); 
    System.out.println(a); 
    System.out.println(); 
} 

머지 소트 방법 : 여기 코드는

public static void mergeSort(ArrayList <Comparable> a, int first, int last){ 
    if(first < last){ 
     int mid = first + (last - first) /2; 
     System.out.println("mergeSorting " + a.subList(first, last + 1)); 
     mergeSort(a, first, mid); 
     System.out.println("mergeSorting " + a.subList(first, mid + 1)); 
     mergeSort(a, mid + 1, last); 
     System.out.println("merging " + a.subList(first, mid + 1) + 
      " and " + a.subList(mid + 1, last + 1)); 
     merge(a, first, mid, last); 
    } 
    System.out.println(); 
    System.out.println("base case"); 
    System.out.println(); 
} 

내가 merge 방법에 문제가 있다고 생각하지만 난 모르겠어요.

내 코드가 잘못 즉를 목록을 정렬 할 것 같다

Input: 
[7,1,9,9,5,4,8,9,10,4] 

Output: 
[4,8,9,4,10,10,5,9,9,7] 

Answer 1

머지 소트 알고리즘은 괜찮습니다. 난 그냥 두 번째 부분은 기본적으로 내가 당신의 표기법을 사용하여 훨씬 간단 뭔가를 대체 있도록 잘못 정확히 알고 정말 어려운 경고

public static void mergeSort(ArrayList <Comparable> a, int first, int last){ 
     if(first < last){ 
      int mid = first + (last - first) /2; 
     // System.out.println("mergeSorting " + a.subList(first, mid)); 
      System.out.println("First"+first); 
      System.out.println("Mid"+mid); 
      System.out.println("Last"+last); 
      System.out.println("MergeSortCall"); 
      System.out.println("firstVector " + a.subList(first, mid+1)); 
      System.out.println("secondVector " + a.subList(mid + 1,last+1));     
      mergeSort(a, first, mid); 
      mergeSort(a, mid + 1, last); 
      merge(a, first, mid, last); 
      System.out.println("mergeVector " + a.subList(first,last+1)); 
     } 

    } 

을 방지하기 위해 ArrayList의 유형을 정의했다. 두 번째 부분은 "병합"알고리즘 일뿐입니다. 그것은 정말로 단순한 것으로되어 있습니다. 어쨌든 이것을 사용하면 결과와 비교할 수 있습니다 (미안하지만 두 번째 부분의 논리를 이해하기 어렵습니다. 숙제입니다.). 가독성을 높이기 위해 두 개의 벡터를 사용하고 있지만 한 번만 수행하면됩니다.

public static void merge(ArrayList <Comparable> a, int first, int mid, int last){ 
      ArrayList <Comparable> vectorFirst = new ArrayList<Comparable>(); 
      ArrayList <Comparable> vectorSecond = new ArrayList<Comparable>(); 

      for(int k=first;k<=mid;k++){ 
       vectorFirst.add(a.get(k)); 
      } 
      for(int k=mid+1;k<=last;k++){ 
       vectorSecond.add(a.get(k)); 
      } 

      int i=first; 
      int j=mid+1; 
      int k=first-1; 
      while((i<=mid)&(j<=last)){ 
       if(vectorFirst.get(i-first).compareTo(vectorSecond.get(j-mid-1))==-1){ 
        k=k+1; 
        a.set(k,vectorFirst.get(i-first)); 
        i=i+1; 
       } 
       else{ 
        k=k+1; 
        a.set(k,vectorSecond.get(j-mid-1)); 
        j=j+1; 
       } 
      } 
      if(i==mid+1){ 
       while(j<=last){ 
        k=k+1; 
        a.set(k,vectorSecond.get(j-mid-1)); 
        j=j+1; 
       } 
      } 
      else{ 
       while(i<=mid){ 
        k=k+1; 
        a.set(k,vectorFirst.get(i-first)); 
        i=i+1; 
       } 
      } 


     }