Здравствуйте, Khimik, Вы писали:

K>2.371 секунды.

K>Да, GPT алгоритм хорошо работает: то ли потому что не использует вычисления с плавающей точкой, то ли потому что не выделяет дополнительную память для массива, то ли сам алгоритм в принципе лучше — честно говоря я ещё до конца не понял что это за строки Inc(i); Dec(j);. А вы поняли?
K>Надо ещё протестировать.


Стандартный алгоритм из Delphi использует примерно такой же алгоритм. Но он медленней из-за универcальности.

class procedure TArray.QuickSort<T>(var Values: array of T; const Comparer: IComparer<T>;
  L, R: Integer);
var
  I, J: Integer;
  pivot, temp: T;
begin
  if L < R then
  begin
    repeat
      if (R - L) = 1 then
      begin
        if Comparer.Compare(Values[L], Values[R]) > 0 then
        begin
          temp := Values[L];
          Values[L] := Values[R];
          Values[R] := temp;
        end;
        break;
      end;
      I := L;
      J := R;
      pivot := Values[L + (R - L) shr 1];
      repeat
        while Comparer.Compare(Values[I], pivot) < 0 do
          Inc(I);
        while Comparer.Compare(Values[J], pivot) > 0 do
          Dec(J);
        if I <= J then
        begin
          if I <> J then
          begin
            temp := Values[I];
            Values[I] := Values[J];
            Values[J] := temp;
          end;
          Inc(I);
          Dec(J);
        end;
      until I > J;
      if (J - L) > (R - I) then
      begin
        if I < R then
          QuickSort<T>(Values, Comparer, I, R);
        R := J;
      end
      else
      begin
        if L < J then
          QuickSort<T>(Values, Comparer, L, J);
        L := I;
      end;
    until L >= R;
  end;
end;

K>Ну и как он вызывается?

TList<T>.Sort

Здравствуйте, Khimik, Вы писали:

K>2.371 секунды.

K>Да, GPT алгоритм хорошо работает: то ли потому что не использует вычисления с плавающей точкой, то ли потому что не выделяет дополнительную память для массива, то ли сам алгоритм в принципе лучше — честно говоря я ещё до конца не понял что это за строки Inc(i); Dec(j);. А вы поняли?
K>Надо ещё протестировать.


Стандартный алгоритм из Delphi использует примерно такой же код. Но он медленней из-за универcальности.

class procedure TArray.QuickSort<T>(var Values: array of T; const Comparer: IComparer<T>;
  L, R: Integer);
var
  I, J: Integer;
  pivot, temp: T;
begin
  if L < R then
  begin
    repeat
      if (R - L) = 1 then
      begin
        if Comparer.Compare(Values[L], Values[R]) > 0 then
        begin
          temp := Values[L];
          Values[L] := Values[R];
          Values[R] := temp;
        end;
        break;
      end;
      I := L;
      J := R;
      pivot := Values[L + (R - L) shr 1];
      repeat
        while Comparer.Compare(Values[I], pivot) < 0 do
          Inc(I);
        while Comparer.Compare(Values[J], pivot) > 0 do
          Dec(J);
        if I <= J then
        begin
          if I <> J then
          begin
            temp := Values[I];
            Values[I] := Values[J];
            Values[J] := temp;
          end;
          Inc(I);
          Dec(J);
        end;
      until I > J;
      if (J - L) > (R - I) then
      begin
        if I < R then
          QuickSort<T>(Values, Comparer, I, R);
        R := J;
      end
      else
      begin
        if L < J then
          QuickSort<T>(Values, Comparer, L, J);
        L := I;
      end;
    until L >= R;
  end;
end;

K>Ну и как он вызывается?

TList<T>.Sort