공허 병합 정렬 방법 java

Question

그래서 컴퓨터 과학 선생님이 copyPartArray를 제외하고 여기 모든 메소드를 무효화하라고 말씀하셨습니다. 나는 이것을 시도하는 방법을 모른다. 시도 할 때 단순히 실패한다.

public static void mergeSort(ArrayList<String> a) { 
    int mid = a.size()/2 - 1; 
    if (a.size() <= 1) 
     return; 
    mergeSort(copyPartArray(a, 0, mid)); 
    mergeSort(copyPartArray(a, mid + 1, a.size() - 1)); 
    merge(a, copyPartArray(a, 0, mid), 
      copyPartArray(a, mid + 1, a.size() - 1)); 
} 

과 모두 함께 mergeSortHelper 제거 :

public static ArrayList<String> mergeSortHelper(ArrayList<String> a) { 
    int mid = a.size()/2 - 1; 
    if (a.size() <= 1) 
     return a; 
    return merge(mergeSortHelper(copyPartArray(a, 0, mid)), 
      mergeSortHelper(copyPartArray(a, mid + 1, a.size() - 1))); 
} 

public static void mergeSort(ArrayList<String> a) { 
    ArrayList<String> x = mergeSortHelper(a); 
    for (int i = 0; i < a.size(); i++) { 
     a.set(i, x.get(i)); 
    } 
} 
    public static ArrayList<String> merge(ArrayList<String> a, 
     ArrayList<String> b) { 
    ArrayList<String> x = new ArrayList<String>(a.size() + b.size()); 
    int aCount = 0; 
    int bCount = 0; 
    for (int i = 0; i < a.size() + b.size(); i++) { 
     if (aCount > a.size() - 1) { 
      for (int j = bCount; j < b.size(); j++) { 
       x.add(b.get(j)); 
      } 
      break; 
     } 
     if (bCount > b.size() - 1) { 
      for (int j = aCount; j < a.size(); j++) { 
       x.add(a.get(j)); 
      } 
      break; 
     } 
     if ((a.get(aCount)).compareTo(b.get(bCount)) < 0) { 
      x.add(a.get(aCount)); 
      aCount++; 
     } else { 
      x.add(b.get(bCount)); 
      bCount++; 
     } 
    } 
    return x; 
} 

    public static ArrayList<String> copyPartArray(ArrayList<String> a, int s, 
     int e) { 
    ArrayList<String> x = new ArrayList<String>(); 
    for (int i = s; i <= e; i++) { 
     x.add(a.get(i)); 
    } 
    return x; 

나는 내 머지 소트를 변경하는 것을 시도했다.

지금 내가 가진 :

public static void mergeSort(ArrayList<String> a, int start, int end) { 
    int mid = (start + end)/2; 
    if (a.size() <= 1) 
     return; 
    mergeSort(a, start, mid); 
    mergeSort(a, mid + 1, end); 

은 어떻게 이것으로 내 병합 방법을 통합 할 것인가?

Answer 1

copyPartArray 배열의 복사본을 만들어서 좋지 않으므로 강사가 참조로 배열을 전달한 다음 시작/끝 (또는 시작/길이) 정수를 전달하기를 원합니다. 이 같은 일을보십시오 :

public static void mergeSort(ArrayList<String> a, int start, int length) { 
    // refer to 'the array' as a[start] to a[start + length] 
} 

a는 당신이 반환 값이 필요하지 않습니다 의미 참조에 의해 전달됩니다.

따라서 start 및 length을 가져와 copyPartArray을 제거하면 한 배열에서 병합 할 수 있습니다.

my blog post on Quicksort에서이 방법을 사용합니다.