Сортировка связного списка (Vkjmnjkftg vfx[ukik vhnvtg)
![]() | В статье не хватает ссылок на источники (см. рекомендации по поиску). |
Сортировка связного списка. Подавляющее большинство алгоритмов сортировки требует для своей работы возможности обращения к элементам сортируемого списка по их порядковым номерам (индексам). В связных списках, где элементы хранятся неупорядоченно, обращение к элементу по его номеру — довольно ресурсоёмкая операция, требующая в среднем сравнений и обращений к памяти. В результате применение типичных алгоритмов сортировки становится крайне неэффективным. Однако у связных списков есть преимущество: возможность объединить два отсортированных списка в один за время без использования дополнительной памяти.
Объединение двух упорядоченных списков
[править | править код]Пусть у нас есть односвязный список, элементы которого описаны структурой (пример на языке 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 элемента может быть использован для сортировки списков длиной до 4294 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;
См. также
[править | править код]Литература
[править | править код]- Shene, Ching-Kuang. "A comparative study of linked list sorting algorithms." 3C ON-LINE 3.2 (1996): 4-9.