Endless loop in QuickSort
Original Reporter info from Mantis: Chuck
-
Reporter name: Chuck Norris
Original Reporter info from Mantis: Chuck
- Reporter name: Chuck Norris
Description:
On a customer*s PC I could see that the QuickSort implementation in Classes.pas led to an endless loop. A Delphi like implementation solved the issue.
{code}
Procedure QuickSort(aList: TJSValueDynArray; L, R : Longint;
const Compare: TListSortCompareFunc);
var
I, J: Longint;
P, T: JSValue;
begin
if L < R then
begin
repeat
if (R - L) = 1 then
begin
if Compare(aList[L], aList[R]) > 0 then
begin
T := aList[L];
aList[L] := aList[R];
aList[R] := T;
end;
break;
end;
I := L;
J := R;
P := aList[(L + R) shr 1];
repeat
while Compare(aList[I], P) < 0 do
Inc(I);
while Compare(aList[J], P) > 0 do
Dec(J);
if I <= J then
begin
if I <> J then
begin
T := aList[I];
aList[I] := aList[J];
aList[J] := T;
end;
Inc(I);
Dec(J);
end;
until I > J;
if (J - L) > (R - I) then
begin
if I < R then
QuickSort(aList, I, R, Compare);
R := J;
end
else
begin
if L < J then
QuickSort(aList, L, J, Compare);
L := I;
end;
until L >= R;
end;
end;
{code}
Mantis conversion info:
- Mantis ID: 38871
- Build: 2.0
- Fixed in version: trunk
- Fixed in revision: 1185.