View Issue Details

IDProjectCategoryView StatusLast Update
0038871pas2jsrtlpublic2021-05-12 18:59
ReporterChuck Norris Assigned ToMichael Van Canneyt  
PrioritynormalSeverityminorReproducibilityunable to reproduce
Status resolvedResolutionfixed 
Fixed in Versiontrunk 
Summary0038871: Endless loop in QuickSort
DescriptionOn 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}
TagsNo tags attached.
Fixed in Revision1185.
Attached Files

Activities

Mattias Gaertner

2021-05-12 16:07

manager   ~0130833

What do you mean with "Delphi like implementation"?
If it copied from Delphi, we cannot use this patch, due to license.

Michael Van Canneyt

2021-05-12 18:59

administrator   ~0130840

Replaced with FPC version of quicksort algorithm. Please test and close if OK

Issue History

Date Modified Username Field Change
2021-05-10 20:06 Chuck Norris New Issue
2021-05-12 16:07 Mattias Gaertner Assigned To => Mattias Gaertner
2021-05-12 16:07 Mattias Gaertner Status new => feedback
2021-05-12 16:07 Mattias Gaertner Note Added: 0130833
2021-05-12 18:59 Michael Van Canneyt Assigned To Mattias Gaertner => Michael Van Canneyt
2021-05-12 18:59 Michael Van Canneyt Status feedback => resolved
2021-05-12 18:59 Michael Van Canneyt Resolution open => fixed
2021-05-12 18:59 Michael Van Canneyt Fixed in Version => trunk
2021-05-12 18:59 Michael Van Canneyt Fixed in Revision => 1185.
2021-05-12 18:59 Michael Van Canneyt Note Added: 0130840