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


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

В предложенной реализации используется стек списков. Необходимый размер стека равен [log2n] + 1, где n — количество элементов списка. Если количество элементов заранее не известно, то можно заранее заложить достаточную глубину стека. Так, например, стек глубиной в 32 элемента может быть использован для сортировки списков длиной до 4 294 967 295 элементов. В стеке сохраняются указатели на отсортированные части списка и уровень — число фактически равное log2i + 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;