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

В статье не хватает ссылок на источники (см. рекомендации по поиску). Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (21 февраля 2017)

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