Сортировка связанного списка без повторного связывания узлов

Question

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

Вот пример:

for(Node<E> x = head.next; x != null; x = x.next) {
    E temp = x.element;
    Node<E> y = x.previous;
    Node<E> p = y.next;
    for(; y != null && y.element.compareTo(temp) > 0; y = y.previous) {
        p = y;
        y.next.setElement(y.element);                
    }
    p.setElement(temp);
}

Это работает правильно.

Теперь мой вопрос: я обманываю, если я делаю что-то подобное вместо сложной перекомпоновки узлов, и это плохая практика для сортировки связанного списка?

Answer 1

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

Но, скажем, ваш узел является более сложным объектом. Копирование содержимого может выглядеть не очень хорошо с точки зрения читабельности. Или, ваш вариант использования требует ссылок подкачки, тогда лучше переставить узлы для удобства чтения и вариант, только когда вам нужно поменять местами ссылки.

Answer 2

Алгоритм сортировки: [выделение добавлено]

В компьютерной науке алгоритм сортировки - это алгоритм, который помещает элементов списка в определенном порядке.

Элементом связанного списка является узел , который состоит из data и reference (ссылка) на следующий узел в списке.

При сортировке связанного списка вы только перемещаете / размещаете часть data элемента связанного списка в правильное положение, но ссылочная часть по-прежнему является ссылкой к тому же следующему узлу. Когда вы распечатываете список после сортировки, вы получите выходные данные в отсортированном порядке, но на самом деле вы переместили только часть data , а не все элементы списка, что, я считаю, не является подходящим способом сортировка связанного списка.

Рассмотрим пример:
Дважды связанный список с ele в качестве члена класса, который содержит данные типа int, а previous и next являются членами, которые сохранить предыдущую и следующую ссылку на узел. Класс Node будет выглядеть примерно так:

class Node{  
    int ele;  
    Node previous;
    Node next;
    ....
    ....
}  

Теперь вы написали код для размещения значения элемента ele в нужном месте при сортировке.

Предположим, вам нужно добавьте еще немного информации в узел вашего связанного списка:

class Node{
    int element;
    char char_ele;    // newly added member
    string str_ele;   // newly added member
    Node previous;
    Node next;
    ....
    ....
}

Теперь с этим изменением вы должны внести изменения в свой код сортировки, чтобы поместить char_ele и str_ele в нужное место вместе с ele при сортировке. Но если вы реализуете правильную сортировку связанного списка, в которой узлы перекомпоновываются на основе условия сортировки, вам не нужно вносить какие-либо изменения в вашу реализацию независимо от изменений в data части узла.

Answer 3

Я не думаю, что это плохая практика. Это даже то, что делает Java List.sort тоже, за исключением того, что идет еще дальше и сортирует элементы вне списка в массиве:

получает массив, содержащий все элементы в этом списке, сортирует массив и выполняет итерации по этому списку, сбрасывая каждый элемент с соответствующей позиции в массиве

Code (из OpenJDK, didn Oracle онлайн):

    default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }

Answer 4

На самом деле это решение вопроса для интервью: «сортируйте связанный список, не меняя следующего поля». Однако - это разновидность мошенничества с использованием самых простых средств, поскольку он не показывает никакой способности обрабатывать указатели. С помощью указателей вы можете изменить голову или следующее поле. Пока узлы не открыты для публикации c (что в любом случае было бы плохой идеей), ваша версия работает.

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

Информация:

Вы идете для i в 0 .. N, для j в i + 1 .. N, который имеет сложность порядка O (N²) - квадрати c. В 3 раза больше элементов, в 9 раз медленнее.

Для массивов можно получить O (N log N), что значительно быстрее.