Сортировка однонаправленного списка

← →
Val (2002-05-22 15:07) [0]

Помогите пожалуйста алгоритмом на данную тему, пробовал делать стандартно, сменой соседних элементов, но запутался совершенно :(
Текст позорных изысканий привожу.
procedure SortList; var BinElement: PointerToDevice; i,j: word; begin for i := 0 to Count-1 do begin CurrentListElement := FirstListElement; while CurrentListElement^.Next <> nil do begin if CurrentListElement^.Value.Weight > CurrentListElement^.Next^.Value.Weight then begin BinElement := CurrentListElement^.Next; CurrentListElement^.Next^.Next := CurrentListElement; CurrentListElement^.Next := BinElement^.Next; end; CurrentListElement := CurrentListElement^.Next; end; end; end;

← →
Lord Warlock (2002-05-22 15:15) [1]

BinElement := CurrentListElement;
CurrentListElement:=CurrentListElement^.Next;
CurrentListElement^.Next:= BinElement;

← →
McSimm (2002-05-22 15:20) [2]

>Val © (22.05.02 15:07)
Похоже все нормально, за исключением ньюанса
Надо менять ссылку у предыдущего для CurrentListElement элемента.

Заведи переменную (изначально присвой nil) и при обмене двух элементов пишешь
if PrevListElement <> nil then
PrevListElement^.Next := BinElement

← →
vuk (2002-05-22 15:25) [3]

Если количество элементов в списке не очень большое, то можно просто свалить их в массив, отсортировать тем же QuickSort и перестроить список заново. Хотя у меня где-то был вариант QuickSort, переработанный для сортировки списков... Иногда проще может оказаться проще постоянно поддерживать список в сортированном состоянии.

← →
Lord Warlock (2002-05-22 15:26) [4]

> Похоже все нормально

Да гдеж нормально!!!

он же за два элемента вперед запрыгивает!

CurrentListElement^.Next^.Next - это что??

← →
McSimm (2002-05-22 15:32) [5]

Все правильно.
> CurrentListElement^.Next^.Next - это что??
Это поле Next второго элемента. Ему присваивается значение ссылки на первый элемент.

Недоделка в том, что тот элемент, который указывал на первый, продолжает на него указывать, а должен после обмена указывать на второй

← →
Lord Warlock (2002-05-22 15:48) [6]

> McSimm ©

да, звиняюсь, забыл что связи тоже нужно перетаскивать...

вот еще один позор, работает или нет, не знаю не проверил за недостатком времени

for i := 0 to Count-1 do
begin
CurrentListElement := FirstListElement;
PrevListElement:= FirstListElement;
while CurrentListElement^.Next <> nil do
begin
if CurrentListElement^.Value.Weight > CurrentListElement^.Next^.Value.Weight then
begin
BinElement := CurrentListElement^.Next;
CurrentListElement^.Next := CurrentListElement^.Next^.Next
BinElement^.Next:=CurrentListElement;
PrevListElement^.Next:=BinElement;
end;
PrevListElement:=CurrentListElement;
CurrentListElement := CurrentListElement^.Next;
end;

← →
Andrey007 (2002-05-22 15:52) [7]

Я не понял задачу. Вам TList надо отсортировать, что ли?

← →
McSimm (2002-05-22 16:19) [8]

>Lord Warlock © (22.05.02 15:48)
не верно. Глубоко не вникал, но если менятся будут первые два элемента списка, будет ошибка. Смотри мои сообщения выше.

>Andrey007 (22.05.02 15:52)
Нет

← →
PVOzerski (2002-05-22 16:27) [9]

IMHO, такой путь вообще крайне медленный, даже при его успешной реализации. Если память не лимитирует, имеет смысл сделать такую штуку:

var
SortAccel:array of указатель_на_структуру;
Mover:указатель_на_структуру;
Temp:структура_того_же_типа_что_поле_Value;
....
SetLength(SortAccel,Count);
Mover:=FirstListElement;
for i:=0 to pred(Count)do
begin
SortAccel[i]:=Mover;
Mover:=Mover.Next;
end;
for i:=0 to Count-2 do
for j:=succ(i)to pred(Count)do
if SortAccel[i].Value.Weight>SortAccel[j].Value.Weight then
begin
Temp:=SortAccel[i].Value;
SortAccel[i].Value:=SortAccel[j].Value;
SortAccel[j].Value:=Temp;
end;
SetLength(SortAccel,0);

← →
Lord Warlock (2002-05-22 16:29) [10]

> McSimm ©

в общем подзабыл я эти указатели :(

я делал класс в котором реализован двунаправленный список и все было гораздо проще...

← →
Lord Warlock (2002-05-23 09:17) [11]

Пока не добью, не отстану :)

итак,

var TempElement: PointerToDevice <-добавить

for i := 0 to Count-1 do <-не понял, зачем это, сортируем список
< Count раз ?
begin
CurrentListElement := FirstListElement; <-верно
BinElement := FirstListElement; <- добавть
while CurrentListElement^.Next <> nil do
begin
if CurrentListElement^.Value.Weight > CurrentListElement^.Next^.Value.Weight then
begin
BinElement^.Next := CurrentListElement^.Next;
TempElement:=CurrentListElement^.Next;
CurrentListElement^.Next := CurrentListElement^.Next^.Next;
TempElement^.Next:=CurrentListElement;
end;
BinElement:=CurrentListElement //Запоминаем предыдущий
CurrentListElement := CurrentListElement^.Next;
end;
end;

по логике вороде так...
проверяйте

← →
McSimm (2002-05-23 10:33) [12]

>Пока не добью, не отстану :)
Зачем, я же еще в первом своем посте написал достаточно для решения проблемы.

>не понял, зачем это, сортируем список Count раз ?
Нет сортируем, 1 раз, но для этого Count проходов.
Алгоритм сортировки. В принципе можно немного оптимизировать, если внутренний цикл каждый раз делать на 1 короче предыдущего, т.к. после первого прохода последний элемент уже на своем месте, после второго предпоследний и т.д.

>проверяйте
Так сам и проверь, не трудно. Раз проблема так задела...

← →
Val (2002-05-23 10:40) [13]

>PVOzerski © (22.05.02 16:27)
идея хоршая конечно, но по чеку делфи5 по привычку щелкнул, на 7-ом паскале это делаю, а там массивы открытого типа присутствуют только в качестве параметров процедур/функций. :(
> McSimm ©
Спасибо за совет, думаю, можно начать со второго элемента списка а первый взять как Prev и т.д. Но предполагаю еще одну проблему, которая может возникнуть - работа со списком начинается, классически, с первого элемента и т.д. по указателям, пока не встретим nil можем производить какие-либо действия над всеми его элементами.
Вовремя сортировки FirstListElement может оказаться где угодно в списке, т.е., как-то надо определять первый элемент и записывать его адрес в FirstListElement.
>Lord Warlock © (23.05.02 09:17)
спасибо за активную помощь, ваш последний код еще не проверял, но почему был наружный цикл могу объяснить: когда вы пробегаете в while по списку, вы сравниваете только соседние элементы между собой и меняете их местами, а нужно сравнить между собой все элементы, для этого сравнение и смена мест производится столько раз, сколько элементов в списке, каждый раз начиная с его начала.

← →
McSimm (2002-05-23 11:07) [14]

>Вовремя сортировки FirstListElement может оказаться где угодно в списке
Действительно. Об этом я не подумал. Предлагаю решение сразу для двух проблем.

Исходный вариант. Изменения:
Перед нутренним циклом:
PrevListElement := nil;

При обмене (последняя операция):
if (PrevListElement = nil) then FirstListElement := BinElement else PrevListElement^.Next := BinElement;

После if...then begin...end; :
PrevListElement := CurrentListElement;
CurrentListElement := CurrentListElement^.Next;

При этом вроде бы поддерживается ссылка от пред. элемента и актуальность FirstListElement.

← →
Val (2002-05-23 12:24) [15]

>McSimm © (23.05.02 11:07)
PrevListElement := CurrentListElement;
Вот тут несостыковка получается, поскольку мы меняем местами текущий элемент со следующим, то нужно PrevListElement присваивать не текущий элемент, а тот с которым они поменялись местами.

← →
PVOzerski (2002-05-23 12:57) [16]

2 Val © (23.05.02 10:40)
>идея хоршая конечно, но по чеку делфи5 по привычку щелкнул, на 7-ом паскале это делаю,

Идеей этой я сам регулярно пользуюсь, с тем различием, что в проектах, написанных
на D3, как у меня (а в D5 не должно бы возникать этой проблемы...) динамических
массивов нет, поэтому код чуть-чуть отличается:
в описании:
type
tSortAccel=array[0..0]of указатель_на_структуру;
pSortAccel=^tSortAccel;
...
var
SortAccel:pSortAccel;

Вместо SetLength(SortAccel,Count):
GetMem(SortAccel,sizeof(tSortAccel)*Count);

Вместо SetLength(SortAccel,0):
ReallocMem(SortAccel,0);

Если можно, переведите на более общепринятый язык фразу:
"но по чеку делфи5 по привычку щелкнул" - а то понять её не могу :^(

← →
Val (2002-05-23 13:10) [17]

>PVOzerski © (23.05.02 12:57)
Если можно, переведите ...
извиняюсь за косноязычие, этот набор слов означал: при формировании вопроса, ошибочно отметил птичкой, что я пользуюсь для решения задачи Delphi 5, хотя решаю данную задачу на Turbo Pascal 7.0.
Большое спасибо за совет. Обязательно им воспользуюсь. Но хотелось бы решить задачу и сменой элементов, уже взяло за живое, упорно что-то упускаю :(

← →
Val (2002-05-23 13:15) [18]

Начудил такой код, но где-то упущение :( первый элемент со вторым меняются, а дальше список состоит из нескольких экземпляров только второго элемента:
procedure SortList; var PrevElement,BinElement: PointerToDevice; i,j: word; begin for i := 0 to Count-1 do begin CurrentListElement := FirstListElement; PrevElement := nil; while CurrentListElement^.Next <> nil do begin if CurrentListElement^.Value.Weight > CurrentListElement^.Next^.Value.Weight then begin BinElement := CurrentListElement^.Next; CurrentListElement^.Next^.Next := CurrentListElement; CurrentListElement^.Next := BinElement^.Next; if (PrevElement = nil) then begin FirstListElement := BinElement ; PrevElement := FirstListElement; end else begin PrevElement^.Next := BinElement; PrevElement := PrevElement^.Next; end; end else begin PrevElement := CurrentListElement; CurrentListElement := CurrentListElement^.Next; end; end; end; end;

← →
McSimm (2002-05-23 13:21) [19]

Вот, чтобы закрыть тему. Проверено:
Для Count элементов:
(добавлена оптимизация внутреннего цикла)

procedure SortList; var i, j: Integer; begin for i := 1 to Count - 1 do begin PrevListElement := nil; CurrentListElement := FirstListElement; for j := 1 to Count - i do begin if CurrentListElement^.Value.Weight > CurrentListElement^.Next^.Value.Weight then begin BinElement := CurrentListElement^.Next; CurrentListElement^.Next := BinElement^.Next; BinElement^.Next := CurrentListElement; CurrentListElement := BinElement; if (PrevListElement = nil) then FirstListElement := BinElement else PrevListElement^.Next := BinElement; end; PrevListElement := CurrentListElement; CurrentListElement := CurrentListElement^.Next; end; end; end;

← →
Val (2002-05-23 13:25) [20]

Сортировка однонаправленного списка Найти похожие ветки