TList.Sort из Delphi7

← →
pasha_golub © (2009-08-18 15:55) [0]

че-то меня как-то смутил сабж.

Допустим имеем:
function Compare(Item1, Item2: Pointer): Integer; begin Result := 0; end; var List: TList; List.Sort(Compare);

В итоге список (по моему разумению) должен остаться без изменений ибо результаты всех сравнений "равно между собой".

Однако объекты (или чего вы там туда засунете) окажутся в обратном порядке.

Исходя из условия сравнения результат, конечно, корректный. На как-то я надеялся на более адекватное поведение. Мне важно чтобы в пределах групп не было перестановок.

← →
Медвежонок Пятачок © (2009-08-18 16:08) [1]

очевидно что чтобы было "как хочется" надо рулить резалтом в соответствии с хотением

← →
pasha_golub © (2009-08-18 16:12) [2]

> Медвежонок Пятачок © (18.08.09 16:08) [1]

Гуд. Пример. А я и рулю. Я говорю явно, что все мои итемы одинаковы. какого их надо переставлять?

← →
pasha_golub © (2009-08-18 16:15) [3]

Исходный код из Classes.pas
procedure QuickSort(SortList: PPointerList; L, R: Integer; SCompare: TListSortCompare); var I, J: Integer; P, T: Pointer; begin repeat I := L; J := R; P := SortList^[(L + R) shr 1]; repeat while SCompare(SortList^[I], P) < 0 do Inc(I); while SCompare(SortList^[J], P) > 0 do Dec(J); if I <= J then begin T := SortList^[I]; SortList^[I] := SortList^[J]; SortList^[J] := T; Inc(I); Dec(J); end; until I > J; if L < J then QuickSort(SortList, L, J, SCompare); L := I; until I >= R; end;

Как оно должно выглядеть по моему разумению:

procedure QuickSort(SortList: PPointerList; L, R: Integer; SCompare: TListSortCompare); var I, J: Integer; P, T: Pointer; begin repeat I := L; J := R; P := SortList^[(L + R) shr 1]; repeat while SCompare(SortList^[I], P) < 0 do Inc(I); while SCompare(SortList^[J], P) > 0 do Dec(J); if (I <= J) and SCompare(SortList^[I], SortList^[J]) <> 0) then begin T := SortList^[I]; SortList^[I] := SortList^[J]; SortList^[J] := T; Inc(I); Dec(J); end; until I > J; if L < J then QuickSort(SortList, L, J, SCompare); L := I; until I >= R; end;

Жду камней.

← →
Palladin © (2009-08-18 16:15) [4]

да... такое дело имеет место быть и в Д6...

← →
pasha_golub © (2009-08-18 16:17) [5]

скобка лишняя одна справа

← →
pasha_golub © (2009-08-18 16:18) [6]

if (I <= J) and (SCompare(SortList^[I], SortList^[J]) <> 0) then

← →
Сергей М. © (2009-08-18 16:18) [7]

> Однако объекты (или чего вы там туда засунете) окажутся
> в обратном порядке

А не фиолетово ли в каком они окажутся порядке, если ты сам сказал. что они "равны" ?

← →
Palladin © (2009-08-18 16:21) [8]

> [5] pasha_golub © (18.08.09 16:17)

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

← →
pasha_golub © (2009-08-18 16:22) [9]

Вообщем зря я это возникал, как оказалось. КвикСорт неустойчив по определению. Мое условие только приближает его к устойчивости. Вот, чего не пузырем сделать было... :))

← →
pasha_golub © (2009-08-18 16:24) [10]

> Сергей М. © (18.08.09 16:18) [7]
>
>

> А не фиолетово ли в каком они окажутся порядке, если ты
> сам сказал. что они "равны" ?

По сути тут два условия сравнения. И как верно подметил Palladin [8], нужно надгородить еще один ключ. Поэтому проще воспользоваться устойчивым алгоритмом.

Сабж просто возник из-за незнания о неустойчивости quickSort"a, а то я бы помалкивал :))

> pasha_golub (18.08.2009 16:22:09) [9]

Сортировка разрушающая, но зато быстрая.

какого их надо переставлять?

Побочный эффект алгоритма перебора, который дергает конец списка и расставляет элементы по новой.

так и должно быть - алгоритм быстрой сортировки относится к неустойчивым, то есть имеет право менять порядок одинаковых элементов

> TUser © (18.08.09 17:09) [13]
>
> так и должно быть - алгоритм быстрой сортировки относится
> к неустойчивым, то есть имеет право менять порядок одинаковых
> элементов

Спасибо. Ветку всю я тоже редко читаю ;)

TList.Sort из Delphi7 Найти похожие ветки