Как эффективно отсортировать список узлов со ссылками на следующий и предыдущий узлы?

Question

У меня есть коллекция элементов в random , каждый из которых имеет следующие структуры данных:

// NOTE: Was "Vertex" in the comments...
public class Item
{
    public string Data { get; set; }
}

public class Node
{
    public Item Next { get; set; }
    public Item Previous { get; set; }
}

Пример:

var a = new Item();
var b = new Item();
var c = new Item();
var d = new Item();

var nodeA = new Node() { Previous = null };
var nodeB = new Node() { Previous = a };
nodeA.Next = b;
var nodeC = new Node() { Previous = b };
nodeB.Next = c;
var nodeD = new Node() { Previous = c, Next = null };
nodeC.Next = d;

// This would be input to the sort method (completely random order).
var items = new []{ nodeC, nodeA, nodeD, nodeB };

// Execute sort

// Result: nodeA, nodeB, nodeC, nodeD.

Очевидно, что O (n ² ) решение возможно.Тем не менее, я хотел бы отсортировать их в правильном порядке менее чем за O (n ² ).Это возможно?

Answer 1

Глядя на это ... предполагая, что вы не используете циклические списки, не могли бы вы просто перебрать свой массив случайного порядка, пока не найдете начальный узел (тот, с .Previous == null) и затем вернете узел? Я имею в виду, что одним из преимуществ связанного списка является то, что вам не нужно хранить ссылки на все узлы в отдельной структуре данных, просто соединяйте их все друг с другом. (Ну, в зависимости от того, как используемая языковая реализация выполняет подсчет ссылок и сборку мусора, если это вообще происходит).

Но, по сути, если у вас нет немедленной необходимости после операции получить доступ к элементу на определенном расстоянии от начального узла, я бы рекомендовал просто немедленно возвращать начальный узел при обнаружении и затем лениво присваивать массиву соответствующего размера как вы используете каждый последующий узел. На самом деле, даже если вы создадите новый массив и назначите его, не будет ли наихудший случай по-прежнему просто O (n), где n - это число узлов? O (n), чтобы найти начальный узел, а затем еще один O (n) n, чтобы перебрать список, назначая каждому узлу соответствующий индекс в массиве того же размера, что и ваш входной массив.

<ч />

Исходя из вашего обновленного вопроса, вам может быть полезно реализовать временный набор связанных списков. Первоначально просматривая список, вы проверяете элементы Next и Previous каждого узла, а затем сохраняете Next s и Previous es в объектах типа словаря (я не уверен, что Для этого лучше всего подойдет объект .NET в качестве ключей, с узлами связанного списка, обернутыми вокруг существующих Node s, ссылающихся на Item s как значения. Таким образом, вы создадите ссылки по ходу процесса без какой-либо реальной сортировки и в конечном итоге просто выполните итерацию по вашему временному списку, назначив Node s, обернутые узлами списка, в новый массив для возврата.

Это должно быть лучше, чем O (n ^ 2) из-за того, что доступ к словарям обычно в среднем постоянен (хотя в худшем случае асимптотическое поведение по-прежнему равно O (n)), я считаю.

Answer 2

Я думаю, что сортировка слиянием может работать.Что-то вроде ...

  merge_sort_list(list, chain_length)
  1. if chain_length > 1 then
  2.    merge_sort_list(list, chain_length/2)
  3.    middle_node = step_into_by(list, chain_length)
  4.    merge_sort_list(middle, chain_length - chain_length/2)
  5.    merge_list_halves(list, middle, chain_length)

  merge_list_halves(list, middle, chain_length)
  1. ... you get the idea

Answer 3

Сортировка слиянием приходит на ум ... Я думаю, что это должно быть применимо здесь, и это работает (наихудший случай) в O (n log n).

Сортировка слияниемчасто является лучшим выбором для сортировки связанного списка: в этой ситуации сравнительно легко реализовать сортировку слиянием таким образом, что она требует только Θ (1) дополнительного пространства, а медленная производительность произвольного доступа связанного списка делаетнекоторые другие алгоритмы (например, быстрая сортировка) работают плохо, а другие (например, heapsort) совершенно невозможны.

Редактировать: после повторного чтения вашего вопроса, это не делаетбольше смысла.В основном вы хотите отсортировать так, чтобы элементы были в порядке, указанном в списке?Это выполнимо за линейное время O (n): сначала вы перемещаетесь назад к первому элементу в списке (по ссылкам), а затем просто выводите каждый элемент вперед.Или ваши Next / Previous не ссылки?