java 포크/조인 mergesort가 쉽게 복사 할 수 있도록 업데이트했습니다.

Question

내 목록이 실제로 mergesort별로 정렬되지 않은 오류를 재현하는 완전한 실행 가능한 예제를 만들었습니다. 어떤 콘솔에 프린트되어, -2 -2 -2 -2 22 22, -2. 따라서 mergesort는 목록의 후반부에 영향을주지 않으며 insertSort가 성공적으로 호출되기 때문에 처음 절반 만 정렬됩니다. 어떤 도움이나 제안도 환영합니다. 고맙습니다!

package threadedmergesort; 

import java.util.ArrayList; 
import java.util.Comparator; 
import java.util.concurrent.ForkJoinPool; 
import java.util.concurrent.RecursiveAction; 

public class ThreadedMergeSort implements Comparator<Integer>{ 

    public static void main(String[] args) { 
     ArrayList<Integer> toSort = new ArrayList<Integer>(); 
     toSort.add(1); 
     toSort.add(22); 
     toSort.add(-2); 
     toSort.add(1); 
     toSort.add(22); 
     toSort.add(-2); 
     toSort.add(1); 
     toSort.add(22); 
     toSort.add(-2); 
     toSort.add(1); 
     toSort.add(22); 
     toSort.add(-2); 
     toSort.add(1); 
     toSort.add(22); 
     toSort.add(-2); 
     toSort.add(1); 
     toSort.add(22); 
     toSort.add(-2); 

     ThreadedMergeSort.sort(toSort, 0, toSort.size()-11); 
     for (Integer e: toSort){ 
       System.out.println(e); 
       } 
    } 

    public static void sort (ArrayList<Integer> inputComp){ 
     sort(inputComp, 0, inputComp.size()-1); 
    } 
    public static void sort (ArrayList<Integer> inputComp, int low, int high){ 
     if (high-low< SIZE_LIMIT){ 
      insertionSort(inputComp, low, high); 
      return; 
     } 
     ArrayList<Integer> temp = new ArrayList(inputComp.size()); 
     pool.invoke(new SortTask(inputComp, temp, low, high)); 
     System.out.println("pool.invoke"); 
    } 

    static class SortTask extends RecursiveAction{ 
     ArrayList<Integer> inputComp; 
     ArrayList<Integer> temp; 
     int low; 
     int high; 

     public SortTask(ArrayList<Integer> inputComp, ArrayList<Integer> temp, int low, int high){ 
      this.inputComp=inputComp; 
      this.temp=temp; 
      this.low=low; 
      this.high=high; 
     } 

     @Override 
     protected void compute(){ 
      if (high-low<SIZE_LIMIT){ 
       insertionSort(inputComp, low, high); 
       return; 
      } 
      int middle = (low + high)/2; 
      invokeAll(new SortTask(inputComp, temp, low, middle), new SortTask(inputComp, temp, middle+1, high)); 
      merge(inputComp, temp, low, middle, high); 
     } 
    } 
     @Override 
     public int compare(Integer c1, Integer c2){ 
     if (c1> c2){ 
      return -1; 
     } 
     if (c1 > c2){ 
      return 1; 
     } 
     return 0; 
    } 

    public static void arrayListCopy(ArrayList<Integer> src, int srcPos, ArrayList<Integer> dest, int destPos, int length){ 
     for (int i = 0; i< length; i++){ 
      dest.set(destPos+i, src.get(srcPos+i)); 
     } 
    } 
    private static void merge(ArrayList<Integer> inputComp1, ArrayList<Integer> inputComp2, int low, int middle, int high){ 
     ThreadedMergeSort sort = new ThreadedMergeSort(); 
     if(sort.compare(inputComp1.get(middle), inputComp1.get(middle+1)) <0){ 
      return; 
     } 
     arrayListCopy(inputComp1, low, inputComp2, low, middle-low+1); 
     int i = low; 
     int j = middle+1; 
     int k = low; 
     while(k < j && j <= high){ 
      if(sort.compare(inputComp2.get(i),inputComp1.get(j)) <= 0){ 
       inputComp1.set(k++, inputComp2.get(i++)); 
      } 
      else{ 
       inputComp1.set(k++,inputComp1.get(j++)); 
      } 
     } 
     arrayListCopy(inputComp2, i, inputComp1, k, j-k); 
    } 

    private static void insertionSort(ArrayList<Integer> inputComp, int low, int high){ 
     ThreadedMergeSort sort = new ThreadedMergeSort(); 
     for(int i = low+1; i<=high; i++){ 
      int j = i; 
      Integer entry = inputComp.get(j); 
      while(low<j && sort.compare(entry, inputComp.get(j-1))< 0){ 
       inputComp.set(j,inputComp.get(j-1)); 
       --j; 
      } 
      inputComp.set(j,entry); 
     } 
    } 
    private static final ForkJoinPool pool = new ForkJoinPool(); 
    private static final int SIZE_LIMIT = 8; 
} 

Answer 1

당신이 무엇을 요구하고있어 :

는

ThreadedMergeSort.sort(toSort, 0, toSort.size()-11); 

는 1 또는 11을 찾으시는 것입니까?