У меня проблема с реализацией алгоритма Mergesort для массивов String в отдельном классе - PullRequest
Новая
       25

У меня проблема с реализацией алгоритма Mergesort для массивов String в отдельном классе

0 голосов
/ 17 мая 2019

Я реализовал этот алгоритм из другого вопроса Stackoverflow, который должен работать: Сортировка (имена) с использованием сортировки слиянием

На данный момент это вывод, который я получаю: Апфель Апфель Банане Лимоне Банане 

public class TestMergesort {
    public static void main(String[] args) {
        String[] fruechte = new String[]{"Orange","Apfel","Zitrone","Limone","Banane"};
        Mergesorttwo.mergeSort(fruechte);

        for (int i = 0;i<fruechte.length;i++)
            System.out.print(fruechte[i]+"\t");
    }
}

public class Mergesorttwo {
    public static void mergeSort(String[] arr) {
        if (arr.length > 1) {
            String[] left = new String[arr.length / 2];
            String[] right = new String[arr.length - arr.length / 2];

            for (int i = 0; i < left.length; i++) {
                left[i] = arr[i];
            }
            for (int i = 0; i < right.length; i++) {
                right[i] = arr[i + arr.length / 2];
            }

            mergeSort(left);
            mergeSort(right);
            merge(arr, left, right);

        }
    }

        public static void merge(String[] arr, String[] left, String[] right){
            int l = 0;
            int r = 0;
            for (int i = 0; i < arr.length; i++) {
                if (l < right.length && r < left.length) {
                    if (r>= right.length || (l < left.length &&left[l].compareTo(right[r]) <= 0)) arr[i] = left[l++];
                    else arr[i] = right[r++];;
                }
            }
        }
    }

1 Ответ

0 голосов
/ 17 мая 2019

Просто проверьте ваш алгоритм слияния. Это не может быть правильным. Просто представьте, что он вызывается для массива с 2 элементами, поэтому вы оставили левый и правый как массивы только с 1 элементом. l и r равны 0. Поэтому внутри первого if обе проверки верны, и одному элементу назначен один элемент, а l или r увеличиваются. Теперь первое if больше не будет запускаться, потому что l или r равны 1. Таким образом, второй элемент массива не изменился.

Так что я бы сделал следующие проверки: 

        public static void merge(String[] arr, String[] left, String[] right){
        int l = 0;
        int r = 0;
        for (int i = 0; i < arr.length; i++) {
            if (l < left.length && r < right.length) {
                if (left[l].compareTo(right[r]) <= 0)
                    arr[i] = left[l++];
                else
                    arr[i] = right[r++];;
            } else if (l < left.length) {
                arr[i] = left[l++];
            } else {
                arr[i] = right[r++];
            }
        }
    }

Итак, проверки в основном: элементы слева и справа? Затем возьмите наименьшее значение слева и справа. Если не осталось элементов в обоих, мы проверяем, где находятся элементы, и берем элемент левой или правой стороны.

...