Эффективная сортировка ArrayList

439

04 апреля 2018, 11:13

Нужно написать реализацию функции void merge(ArrayList a, ArrayList b) { // тело функции }

Функция принимает два отсортированных от меньшего к большему ArrayList одинакового размера [a1, a2, ..., an], [b1, b2, ..., bn]. В результате выполнения функции в первом(!) ArrayList (в данном случае это А) должны содержаться элементы обоих ArrayList, также отсортированные от меньшего к большему. Второй ArrayList должен остаться неизменненным. Пример: Входные данные A [1,3,5] B [2,6,8] Результат A [1,2,3,5,6,8] B [2,6,8]

ArrayList a = new ArrayList();
a.add(1);
a.add(3);
a.add(5);
ArrayList b = new ArrayList();
b.add(2);
b.add(6);
b.add(8);
merge(a,b);
void merge(ArrayList a, ArrayList b){
    a.addAll(b);
    Collections.sort(a);
}

помогите разобраться, в чем неэффективный код?

Answer 1

Не эффективность заключается в том, что ты сначала сливаешь два списка, а потом сортируешь. Сортируя, sort() проходит по всему списку не один раз.

Есть другой, более эффективный способ. У тебя два списка отсортированных по возрастанию. Так пройдись в цикле по первому и вставляй элементы второго, где это необходимо. Таким образом ты пройдешь по списку один раз и эффективность будет N, а при сортировке N^2.

Answer 2

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

Но постоянная вставка элементов для ArrayList (в отличии от LinkedList) это весьма трудоемкая операция (т.к. нужно постоянно сдвигать элементы вправо). Поэтому Вы должны определиться, что для Вас важнее - минимизировать расход памяти или максимизировать скорость работы? Если на память никаких условий не накладывается, то эффективнее будет получить все значения в третьем списке, а потом перезалить их в первый