Оптимизация быстрой сортировки (QuickSort) в Delphi

Delphi , Базы данных , Сортировка и Фильтр

QuickSort — это популярный алгоритм сортировки, который используется во многих языках программирования, в том числе и в Delphi. Однако, как и любой другой алгоритм, QuickSort может быть оптимизирован для достижения лучшей производительности. В этой статье мы рассмотрим некоторые аспекты реализации QuickSort в Delphi и поговорим об оптимизации этого алгоритма.

Реализация QuickSort в Delphi

В образцах Delphi можно найти следующую реализацию QuickSort:

procedure QuickSort(var A: array of Integer; iLo, iHi: Integer);
var
  Lo, Hi, Mid, T: Integer;
begin
  Lo := iLo;
  Hi := iHi;
  Mid := A[(Lo + Hi) div 2];
  repeat
    while A[Lo] < Mid do Inc(Lo);
    while A[Hi] > Mid do Dec(Hi);
    if Lo <= Hi then
    begin
      VisualSwap(A[Lo], A[Hi], Lo, Hi); // just for visual
      T := A[Lo];
      A[Lo] := A[Hi];
      A[Hi] := T;
      Inc(Lo);
      Dec(Hi);
    end;
  until Lo > Hi;
  if Hi > iLo then QuickSort(A, iLo, Hi);
  if Lo < iHi then QuickSort(A, Lo, iHi);
  if Terminated then Exit;
end;

Этот код работает, но некоторые аспекты его реализации могут показаться странными. Например, в цикле repeat-until индексы Lo и Hi одновременно увеличиваются и уменьшаются соответственно, даже если один из них уже равен значению Mid. Это может привести к тому, что "пivot" окажется между двумя значениями, а не между Lo и Hi.

Оптимизация для случаев с равными ключевыми значениями

Один из комментаторов предложил следующую оптимизацию для случаев, когда в массиве присутствуют равные ключевые значения:

procedure QuickSort(var A: array of Integer; iLo, iHi: Integer);
var
  Lo, Hi, Mid, T: Integer;
begin
  Lo := iLo;
  Hi := iHi;
  T := (Lo + Hi) div 2;
  VisualSwap(A[Lo], A[T], Lo, T);
  Mid := A[T];
  A[T] := A[Lo];
  A[Lo] := Mid;

  inc(Lo);
  //Mid := A[(Lo + Hi) div 2];
  repeat
    while A[Lo] < Mid do Inc(Lo);
    while A[Hi] > Mid do Dec(Hi);
    if Lo <= Hi then
    begin
      VisualSwap(A[Lo], A[Hi], Lo, Hi);
      T := A[Lo];
      A[Lo] := A[Hi];
      A[Hi] := T;
      Inc(Lo);
      Dec(Hi);
    end;
  until Lo > Hi;

  if Hi > iLo then
  begin
    VisualSwap(A[iLo],A[Hi],iLo,Hi);
    A[iLo] := A[Hi];
    A[Hi] := Mid;
    dec(Hi);
  end;

  if Hi > iLo then QuickSort(A, iLo, Hi);
  if Lo < iHi then QuickSort(A, Lo, iHi);
  if Terminated then Exit;
end;

В этой версии алгоритма ключевое значение выносится за пределы массива, а затем сортировка проводится только для тех элементов, которые находятся вне диапазона, ограниченного ключевым значением.

3-way partitioning

Еще один комментатор предложил использовать 3-way partitioning для решения проблемы с равными ключевыми значениями. Однако, это не является обязательной мерой для решения данной проблемы, так как QuickSort по своей природе не является стабильным алгоритмом сортировки.

Итоги

В заключение можно сказать, что реализация QuickSort в Delphi может быть оптимизирована для достижения лучшей производительности. Однако, некоторые аспекты этой реализации могут показаться странными, и требуют более детального изучения. Одним из возможных направлений для оптимизации является использование 3-way partitioning, но это не является обязательной мерой для решения проблемы с равными ключевыми значениями.

Также стоит отметить, что при использовании QuickSort в Delphi следует учитывать возможность переполнения переменной Mid, если массив находится

Создано по материалам из источника по ссылке.

Оптимизация быстрой сортировки (QuickSort) в Delphi, включая описание реализации алгоритма и обсуждение возможных путей оптимизации.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Сортировка и Фильтр ::