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;

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

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

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

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

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

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