Interested Article - Сортировка связного списка

Сортировка связного списка . Подавляющее большинство алгоритмов сортировки требует для своей работы возможности обращения к элементам сортируемого списка по их порядковым номерам (индексам). В связных списках , где элементы хранятся неупорядоченно, обращение к элементу по его номеру — довольно ресурсоёмкая операция, требующая в среднем ${\frac {n}{2}}$ сравнений и обращений к памяти. В результате применение типичных алгоритмов сортировки становится крайне неэффективным. Однако у связных списков есть преимущество: возможность объединить два отсортированных списка в один за время $O(n+m)$ без использования дополнительной памяти.

Объединение двух упорядоченных списков

Пусть у нас есть односвязный список, элементы которого описаны структурой (пример на языке Pascal ):

  type
    PList_Item = ^TList_Item;
    TList_Item = record
      Key: Integer;
      Next: PList_Item;
    end;
  var
    List: PList_Item; // Указатель на список

Алгоритм достаточно прост: на входе имеются указатели на первые элементы объединяемых списков. Началом результирующего списка из них выбирается элемент с наименьшим ключом. Затем в качестве следующих элементов результирующего списка выбирается последующие элементы из первого или второго исходного списка, с меньшим значением ключа. Когда достигнут последний элемент одного из исходных списков, указатель последнего элемента результирующего списка устанавливается на остаток другого входного списка.

  function IntersectSorted(const pList1, pList2: PList_Item): PList_Item;
  var
    pCurItem: PList_Item;
    p1, p2: PList_Item;
  begin
    p1 := pList1;
    p2 := pList2;
    if p1^.Key <= p2^.Key then 
    begin
      pCurItem := p1;
      p1 := p1^.Next;
    end 
    else begin
      pCurItem := p2;
      p2 := p2^.Next;
    end;
    Result := pCurItem;
    while (p1 <> nil) and (p2 <> nil) do
    begin
      if p1^.Key <= p2^.Key then
      begin
        pCurItem^.Next := p1;
        pCurItem := p1;
        p1 := p1^.Next;
      end 
      else begin
        pCurItem^.Next := p2;
        pCurItem := p2;
        p2 := p2^.Next;
      end;
    end;
    if p1 <> nil then
      pCurItem^.Next := p1
    else
      pCurItem^.Next := p2;
  end;

Сортировка односвязного списка

Процесс сортировки списка представляет из себя последовательный проход по списку с сортировкой сначала пар элементов, затем каждой двойки пар элементов, с объединением в списки из 4х элементов, затем объединяются получившиеся списки из 8, 16 и т. д. элементов.

В предложенной реализации используется стек списков. Необходимый размер стека равен [log ₂ n ] + 1, где n — количество элементов списка. Если количество элементов заранее не известно, то можно заранее заложить достаточную глубину стека. Так, например, стек глубиной в 32 элемента может быть использован для сортировки списков длиной до 4 294 967 295 элементов. В стеке сохраняются указатели на отсортированные части списка и уровень — число фактически равное log ₂ i + 1, где i — количество элементов в этой части списка.

Суть алгоритма в следующем: идёт последовательный обход списка, при этом каждый элемент преобразуется к вырожденному списку, путём удаления указателя на следующий элемент. Указатель на созданный таким образом список помещается в стек, при этом уровень указывается равным 1, после чего проводится проверка: если два последних элемента стека имеют одно и то же значение уровня, то они извлекаются из стека, производится объединение списков, на которые указывают эти элементы, а результирующий список помещается в стек с уровнем на единицу больше предыдущего. Такое объединение повторяется пока уровни двух последних элементов равны, или пока не будет достигнута вершина стека. После того как исходный список полностью пройден, перечисленные в стеке списки объединяются вне зависимости от их уровня. Получившийся в результате объединения список и есть искомый, с отсортированными элементами

type
  TSortStackItem = record
    Level: Integer;
    Item: PList_Item;
  end;
var
  Stack: Array[0..31] of TSortStackItem;
  StackPos: Integer;
  p: PList_Item;
begin
  StackPos := 0;
  p := List;
  while p <> nil do
  begin
    Stack[StackPos].Level := 1;
    Stack[StackPos].Item := p;
    p := p^.Next;
    Stack[StackPos].Item^.Next := nil;
    Inc(StackPos);
    while (StackPos > 1) and (Stack[StackPos - 1].Level = Stack[StackPos - 2].Level) do 
    begin
      Stack[StackPos - 2].Item := IntersectSorted(Stack[StackPos - 2].Item, Stack[StackPos - 1].Item);
      Inc(Stack[StackPos - 2].Level);
      Dec(StackPos);
    end;
  end;
  while StackPos > 1 do
  begin
    Stack[StackPos - 2].Item := IntersectSorted(Stack[StackPos - 2].Item, Stack[StackPos - 1].Item);
    Inc(Stack[StackPos - 2].Level);
    Dec(StackPos);
  end;
  if StackPos > 0 then
    List := Stack[0].Item;
end;

Сложность алгоритма

Очевидно, сложность алгоритма O( n log n ), при этом требования к памяти минимальны O(log n )

Сортировка двусвязного списка

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

  type
    PList_Item = ^TList_Item;
    TList_Item = record
      Key: Integer;
      Prev, Next: PList_Item; 
    end;
  var
    // Указатели на первый и последний элемент списка
    First, Last: PList_Item;

  p := First;
  // Проверка, что список не является пустым
  if p <> nil then
  begin  
    p^.Prev := nil;
    while p^.Next <> nil do
    begin
      p^.Next^.Prev := p;
      p := p^.Next;
    end;
  end;
  Last := p;