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

Сортировка связного списка. Подавляющее большинство алгоритмов сортировки требует для своей работы возможности обращения к элементам сортируемого списка по их порядковым номерам (индексам). В связных списках, где элементы хранятся неупорядоченно, обращение к элементу по его номеру — довольно ресурсоёмкая операция, требующая в среднем ${\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 элемента может быть использован для сортировки списков длиной до 4294 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;

См. также

• Связный список
• Алгоритм сортировки

Литература

• Shene, Ching-Kuang. "A comparative study of linked list sorting algorithms." 3C ON-LINE 3.2 (1996): 4-9.