Сортировка слиянием возвращает ArrayList, состоящий из нескольких дубликатов первой записи, а не отсортированный ArrayList - PullRequest
Новая
       14

Сортировка слиянием возвращает ArrayList, состоящий из нескольких дубликатов первой записи, а не отсортированный ArrayList

2 голосов
/ 22 мая 2019

Вызов метода сортировки слиянием для ArrayList объектов данных возвращает ArrayList, полностью состоящий из первой записи в оригинале ArrayList (оригинал содержал 9 тыс. Отдельных записей, в то время как в «отсортированном» содержалось 9 тыс. Дубликатов).первой записи оригинала).

Я просмотрел код, но не могу понять, почему.Функция работает на ArrayList из JsonObject от javax, и критерием сортировки является поле в пределах указанного JsonObject.Предполагается сравнить строки указанного поля и отсортировать их.

public void sortDataObjects(String identifier, ArrayList<JsonObject> both) {
    ArrayList<JsonObject> left = new ArrayList<>();
    ArrayList<JsonObject> right = new ArrayList<>();
    int size = both.size();
    int midpoint = size / 2;

    if (size == 1) {
        return;
    } else {
        for(int i = 0; i < midpoint; i++) {
            left.add(both.get(i));
        }
        for (int i = midpoint; i < size; i++) {
            right.add(both.get(1));
        }

        sortDataObjects(identifier, left);
        sortDataObjects(identifier, right);

        mergeSortHelper(identifier, left, right, both);
    }
}

public void mergeSortHelper(String identifier, ArrayList<JsonObject> left, ArrayList<JsonObject> right, ArrayList<JsonObject> both) {
    int leftIndex = 0;
    int rightIndex = 0;
    int bothIndex = 0;

    while (leftIndex < left.size() && rightIndex < right.size()) {
        if ((left.get(leftIndex).getString(identifier).compareTo(right.get(rightIndex).getString(identifier))) < 0) {
            both.set(bothIndex, left.get(leftIndex));
            leftIndex++;
        } else {
            both.set(bothIndex, right.get(rightIndex));
            rightIndex++;
        }
        bothIndex++;
    }

    if (leftIndex >= left.size()) {
        // The left ArrayList has been use up...
        for (int i = rightIndex; i < right.size(); i++) {
            both.set(bothIndex, right.get(i));
            bothIndex++;
        }
    } else {
        for (int i = leftIndex; i < left.size(); i++) {
            both.set(bothIndex, left.get(i));
            bothIndex++;
        }
    }
}

Ответы [ 2 ]

2 голосов
/ 22 мая 2019

Ваша ошибка здесь: 

for (int i = midpoint; i < size; i++){
    right.add(both.get(1));
}

Это не помещает вторую половину исходного списка в right.

1 голос
/ 22 мая 2019

Массив right не инициализирован должным образом, назначение right.add(both.get(1)); неверно: существует опечатка, которая может легко остаться незамеченной, 1 для i.

Также было бы целесообразно правильно обрабатывать пустые массивы.

Вот исправленная версия: 

public void sortDataObjects(String identifier, ArrayList<JsonObject> both) {
    int size = both.size();

    if (size > 1) {
        ArrayList<JsonObject> left = new ArrayList<JsonObject>();
        ArrayList<JsonObject> right = new ArrayList<JsonObject>();
        int midpoint = size / 2;

        for(int i = 0; i < midpoint; i++) {
            left.add(both.get(i));
        }
        for (int i = midpoint; i < size; i++) {
            right.add(both.get(i));
        }
        sortDataObjects(identifier, left);
        sortDataObjects(identifier, right);
        mergeSortHelper(identifier, left, right, both);
    }
}
...