| Новости | Поиск | FAQ | Статьи | Книги | Новости VCL | | Форумы ЧАТ | Орешник | KOL и MCK |
Форумы -» Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

	« предыдущая ветвь | форум | следующая ветвь »

TList.Sort и переполнение стека [D7, Win2k]

said46 ©   (2006-12-11 14:26:00) 

Есть объект TList, содержащий указатели на record'ы. Пытаюсь отсортировать.

type
 PTRec = ^TRec;
 TRec = record
...
end;

...
// функция обратного вызова для сортировки
function CompareTRec(Item1, Item2: Pointer): Integer;
begin
 Result := CompareDateTime(PTRec(Item1).RT, PTRec(Item2).RT);
end;

Все работает, однако при сортировке зачем то переставляются местами одинаковые элементы списка.
Изменяю функцию так:

function CompareTRec(Item1, Item2: Pointer): Integer;
var
 res: Integer;
begin
 res := CompareDateTime(PTRec(Item1).RT, PTRec(Item2).RT);
 if res = 0 then res := -1;
 Result := res;
end;

Получаю переполнение стека. Почему?

---

Sha   (2006-12-12 10:02:00) [1]

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

Тебе просто надо использовать сортировку, сохраняющую порядок, или использовать в критерии сортировки поле с уникальным значением, задающим порядок следования равных (по остальным полям) элементов.

---

Sha   (2006-12-12 09:42:00) [2]

Для QuickSort требуется, чтобы результат повторного сравнения любых двух элементов был тем же, что и первый раз. И более того, из (a<=b, b<=c) должно следовать, что a<=c. Иначе аозможен выход за границу массива.

Для HeapSort этого не требуется.

---

said46   (2006-12-12 09:19:00) [3]

> Ну и пусть переставляет, если одинаковые. А если тебя перестановака
> не устраивает, то значит всё-таки не одинаковые :)


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

Рекурсия была из-за парадокса... строка if Result = 0 then Result := -1;подразумевала, что при сравнении элемента с самим с собой результат - он меньше самого себя =) .

Проблемы решилиись изменением функции обратного вызова таким образом:
function CompareTRec(Item1, Item2: Pointer): Integer;
begin
 Result := CompareDateTime(PTRec(Item1)^.RT, PTRec(Item2)^.RT);
 if Result = 0 then Result := -1;
 if Item1 = Item2 then Result := 0;
end;

И переполнения стека нет, и одинаковые элементы не переставляет почем зря...

---

ЮЮ   (2006-12-12 03:18:00) [4]

> Все работает, однако при сортировке зачем то переставляются
> местами одинаковые элементы списка.


Ну и пусть переставляет, если одинаковые. А если тебя перестановака не устраивает, то значит всё-таки не одинаковые :)


> if res = 0 then res := -1;

предположим пришлось сравнить два элемента списка a и b дважды:  
CompareTRec(a, b) и CompareTRec(b, a),
а твоя функция утверждает, что a < b и b < а. Какой угодно алгоритм сортировки на этом зациклится :)

---

clickmaker   (2006-12-11 14:37:00) [5]

> причина переполнения стека

см. реализацию QuickSort в classes.pas
влетаешь в рекурсию

---

MBo   (2006-12-11 14:37:00) [6]

>при сортировке зачем то переставляются местами одинаковые элементы списка

TList использует QuickSort, а эта сортировка неустойчива(т.е. не сохраняет взаимное положение элементов с равными ключами)
Если нужна устойчивая, сортируй сам - при небольшом количестве элементов - вставками, при большом - слиянием

---

said46   (2006-12-11 14:33:00) [7]

Вроде одинаковые... Но это не суть, меня больше интересует причина переполнения стека.

---

clickmaker   (2006-12-11 14:28:00) [8]

> переставляются местами одинаковые элементы списка

может, они не совсем одинаковые?

---

Наверх