Что плохого в этом коде сортировки слиянием, который выполняется ужасно долго? - PullRequest
Новая
       13

Что плохого в этом коде сортировки слиянием, который выполняется ужасно долго?

0 голосов
/ 25 сентября 2018

Итак, приведенный ниже алгоритм работает отлично, для входных размеров - 10,20,30Размер ввода - на выходе видно временное отставание 35Размер ввода - 40 Вы будете ждать некоторое времяВсе, что больше 40 - сортировка не завершена.

public class TestSorting {

    public static void main(String[] args) {

        long start, end;

        Comparable[] numbers = generateRandom(45);
        Comparable[] temp;

        temp = Arrays.copyOf(numbers,numbers.length);
        System.out.println("-----------------------------------------------------------");
        System.out.println("                  M E R G E   S O R T");
        System.out.println("-----------------------------------------------------------");
        System.out.println("Initial: " + Arrays.asList(temp));
        start = System.nanoTime();
        Merge.sort(temp);
        end = System.nanoTime();
        System.out.println("Final  : " + Arrays.asList(temp));
        System.out.println("Total Runtime: " + (end-start));


    }

    private static Comparable[] generateRandom(int size) {
        Comparable[] data = new Comparable[size];

        Random random = new Random();

        for(int i = 0 ;i<size;i++)
            data[i] = random.nextInt(100);

        return data;
    }
}

Merge.java 

public class Merge {

    public static boolean lessThan(Comparable x, Comparable y) {
       return x.compareTo(y)<0;
    }

    public static void sort(Comparable[] data) {
        sort(data,0,data.length-1);
    }


    private static void sort(Comparable[] data,int low,int high) {
        if(high<=low) return;

        int mid = low + (high-low)/2;
        sort(data,0,mid);
        sort(data,mid+1,high);
        merge(data,low,mid,high);
    }

    private static void merge(Comparable[] data, int low, int mid, int high) {

        Comparable[] X = new Comparable[mid-low+1]
        Comparable[] Y = new Comparable[high-mid];

        for(int i=0;i<X.length;i++) X[i] = data[low+i];
        for(int i=0;i<Y.length;i++) Y[i] = data[mid+1+i];

        int start1 = 0, start2 = 0;
        while(start1<X.length && start2<Y.length) {
            if(lessThan(X[start1],Y[start2])) data[low++] = X[start1++];
            else data[low++] = Y[start2++];
        }

        while (start1 < X.length) data[low++] = X[start1++];
        while (start2 < Y.length) data[low++] = Y[start2++];
    }

}

Может кто-нибудь помочь мне разобраться в чем дело?Это создание дополнительных локальных массивов делает его медленным?

1 Ответ

0 голосов
/ 25 сентября 2018

Рекурсивный вызов 

sort(data,0,mid);

должен быть 

sort(data,low,mid);
...