Java сортировка слиянием по строкам работает только с массивом до четырех элементов - PullRequest
Новая
       7

Java сортировка слиянием по строкам работает только с массивом до четырех элементов

0 голосов
/ 01 марта 2020

Я пытаюсь использовать сортировку слиянием для сортировки по алфавиту списка слов, введенных из командной строки. Это работает, когда я сортирую массивы до 4 слов, но когда я пытаюсь использовать пять или более слов: он возвращает массив в неправильном порядке или в том же порядке, в котором он был изначально.

Когда Я отладил его, я понял, что он сортируется правильно вплоть до слияния последних двух половинок. Ex. если это массив данных размером 7, он правильно сортирует слова в позициях 0 - 4 и слова в позициях 5 - 7, но объединяет их в неправильном порядке.

Из-за этого, я полагаю, ошибка в функции mergeSort, поскольку функция слияния работает, учитывая, что ей удалось правильно отсортировать меньшие массивы. Однако я не вижу, как там может быть ошибка, поскольку он просто делит массив пополам и вызывает другие функции.

Сравнивая его с другими функциями слияния, которые я нашел в Интернете и здесь, код очень похож, поэтому мне трудно увидеть свою ошибку.

Ниже приведены слова ввода из cmd и вызывающей сортировки слияния: 

    public static void main(String[] args) {
        List<String> List = new ArrayList<String>();
        Scanner input = new Scanner(System.in); 
        while(input.hasNextLine()){ 
            String word = input.nextLine().trim();
            if (word.equals("")) break;
            List.add(word); 
        }
        input.close();
        System.out.println("unsorted: " + ListA);
        mergeSort(List, 0, List.size()-1);
        System.out.println("sorted: " + ListA);
    }

Моя функция слияния mergeSort и функция слияния следующие: 

    public static void mergeSort(List<String> wordArray, int lower, int upper) {
        if ((upper-lower) >= 1 ) {//if arraylist size is greater than 1
            int halfPt = (upper + lower)/2; //dividing the arraylist
            int s1 = lower;
            int f1 = halfPt;
            int s2 = halfPt +1;
            int f2 = upper;
            mergeSort(wordArray, s1, f1); //mergesort on first half
            mergeSort(wordArray, s2, f2); //mergesort on second half
            merge(wordArray, s1, f1, s2, f2); //merge first and second half
        }
    }

    public static void merge(List<String> wordArray, int s1, int f1, int s2, int f2) {
        List<String> finalArray = new ArrayList<String>();
        while (s1<=f1 && s2<=f2) { //alphabetically sorting both half arrays
            if(wordArray.get(s1).compareTo(wordArray.get(s2))<0) {//placing smallest element first
                finalArray.add(wordArray.get(s1));
                s1++;
            } else {
                finalArray.add(wordArray.get(s2));
                s2++;
            }
        }
        //add leftovers in half-arraylists
        while (s1 <= f1) {
            finalArray.add(wordArray.get(s1));
            s1++;
        }   
        while (s2 <= f2) {
            finalArray.add(wordArray.get(s2));
            s2++;
        }
        for (int i = 0; i < wordArray.size(); i++) { //copy sorted array into original array
            if (wordArray.size()!=finalArray.size()) break;
            wordArray.set(i, finalArray.get(i));
        }
    }

Куда я мог идти? неправильно? Любая помощь очень ценится, и спасибо заранее!

1 Ответ

1 голос
/ 01 марта 2020

Ваша проблема заключается в последнем for loop из merge метода. 

for (int i = 0; i < wordArray.size(); i++) { //copy sorted array into original array
      // This if is source of problem, size of your final array will only match that of
      // wordArray in the last call to merge.
      // In all the other invocations it will not match, hence the copying never occurs in those cases
      if (wordArray.size()!=finalArray.size()) break;
      wordArray.set(i, finalArray.get(i));
}

Чтобы исправить это, измените последний for loop следующим образом. 

// In the beggining of merge method store values of s1 and f2
// so that we know the start and end index of the merge operation
int start = s1;
int end = f2;

// Now modify the last for loop as
for(int i=0; i<finalArray.size() && start <= end; i++, start++){
   wordArray.set(start, finalArray.get(i));
}
...