Как сделать общую сортировку слиянием с компаратором интерфейса Java? - PullRequest
Новая
       22

Как сделать общую сортировку слиянием с компаратором интерфейса Java?

0 голосов
/ 24 марта 2019

Я пытаюсь объединить списки сортировки, но получаю ArrayOutOfBoundsError и не могу это исправить.

Это для общих списков, использующих интерфейс Comparator.Сейчас я запускаю тестирование с Integer.

Это мой класс сортировки слиянием: 

public class ListMS<T> {
    private List<T> wholeList;
    private Comparator<T> comparator;

    public ListMS(List<T> list, Comparator<T> C){
        wholeList=new ArrayList<>();
        wholeList.addAll(list);
        comparator=C;
        mergeSort(wholeList, comparator);

    }

    public static <T> void merge(List<T> L1, List<T> L2,List<T> L, Comparator<T> C){
        int i=0;
        int j=0;
        while(i+j<L.size()){
            if(j==L2.size() || (i<L.size() && C.compare(L1.get(i),L2.get(j))<0)){
                L.set(i+j,L1.get(i++));
            }
            else{
                L.set(i+j,L2.get(j++));
            }
        }
    }

    public static <T> void mergeSort(List<T> L, Comparator<T> C){
        int size=L.size();
        if(size<2){
            return;
        }
        int half=size/2;
        List<T> L1=L.subList(0,half);
        List<T> L2=L.subList(half,size);

        mergeSort(L1,C);
        mergeSort(L1,C);

        merge(L1,L2,L,C);
    }

    public List<T> getWholeList(){
        return wholeList;
    }
}

С чем я тестирую его: 

public static void main(String[] args) {

        Comparator<Integer> C=new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        };

        List<Integer> list1K=generateList(1000);
        ListMS<Integer> list1KMerged=new ListMS<>(list1K, C);

        printList(list1K);
        printList(list1KMerged.getWholeList());


    }


    public static List<Integer> generateList(int size){
        List<Integer> listNumber=new ArrayList<>();
        for(int i=0;i<size;i++){
            int min=0;
            int max=size-1;
            int num=(int)(Math.random() * ((max - min) + 1)) + min;
            listNumber.add(num);
        }
        return listNumber;
    }

    public static void printList(List<Integer> L){
        for(int i=0;i<L.size();i++){
            System.out.print(L.get(i));
        }
    }

НоЯ получаю несколько ArrayOutOfBounds:

Исключение в потоке "main" java.lang.IndexOutOfBoundsException: Index: 1, Size: 1 в java.util.ArrayList $ SubList.rangeCheck (ArrayList.java:1225)в java.util.ArrayList $ SubList.get (ArrayList.java:1042) в ListMS.merge (ListMS.java:19) в ListMS.mergeSort (ListMS.java:40) в ListMS.mergeSort (ListMS.java:37)в ListMS.mergeSort (ListMS.java:37) в ListMS.mergeSort (ListMS.java:37) в ListMS.mergeSort (ListMS.java:37) в ListMS.mergeSort (ListMS.java:37) в ListMS.mergeSort (ListMS).java: 37) в ListMS.mergeSort (ListMS.java:37) в ListMS.mergeSort (ListMS.java:37) в ListMS. (ListMS.java:11) в TestListMS.main (TestListMS.java:16)

1 Ответ

1 голос
/ 24 марта 2019

В основном, в ваших счетчиках циклов в merid () methid есть ошибка в этой строке: 

if(j == L2.size() || (i < L.size() && C.compare(L1.get(i), L2.get(j)) < 0))

Измените функцию слияния следующим образом: 

public static <T> void merge(List<T> L1, List<T> L2,List<T> L, Comparator<T> C){
        int i=0;
        int j=0;
        int k=0;
        while(i < L1.size() && j < L2.size()) {
            if(C.compare(L1.get(i), L2.get(j)) < 0) {
                L.set(k++, L1.get(i++));
            }else {
                L.set(k++, L2.get(j++));
            }   
        }
        while(i < L1.size()) {
            L.set(k++, L1.get(i++));
        }
        while(j < L2.size()) {
            L.set(k++, L2.get(j++));
        }
    }

ОБНОВЛЕНИЕ:

В функции mergeSort также есть несколько ошибок.Измените его следующим образом: 

public static <T> void mergeSort(List<T> L, Comparator<T> C){
    int size=L.size();
    if(size<2){
        return;
    }
    int half=size/2;
    List<T> L1=new ArrayList<T>(L.subList(0,half));
    List<T> L2=new ArrayList<T>(L.subList(half,size));

    mergeSort(L1,C);
    mergeSort(L2,C);

    merge(L1,L2,L,C);
    printList(L);
}

L1 и L2 не были новыми списками массивов в старом коде.Это были всего лишь два указателя, указывающие на те же области памяти, что и в списке L. Поэтому изменение L в функции слияния также изменило L1 и L2.Чтобы решить эту проблему, вам нужно создать два новых подмассива с отдельными выделениями памяти.

Также вы дважды вызывали mergeSort(L1,C); вместо того, чтобы вызывать его на L1 и L2 каждый.

...