Скачать: CL | DM;

TList.Sort и переполнение стека   Найти похожие ветки 

← →
said46   (2006-12-11 14:26) [0]

Есть объект 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;

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

---

← →
clickmaker ©   (2006-12-11 14:28) [1]

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

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

---

← →
said46   (2006-12-11 14:33) [2]

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

---

← →
clickmaker ©   (2006-12-11 14:37) [3]

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

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

---

← →
MBo ©   (2006-12-11 14:37) [4]

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

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

---

← →
ЮЮ ©   (2006-12-12 03:18) [5]

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


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


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

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

---

← →
said46   (2006-12-12 09:19) [6]

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


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

Рекурсия была из-за парадокса... строка 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;

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

---

← →
Sha ©   (2006-12-12 09:42) [7]

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

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

---

← →
Sha ©   (2006-12-12 10:02) [8]

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

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

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.47 MB
Время: 0.028 c