Как реализовать алгоритм быстрой сортировки QuickSort для сортировки по возрастанию и убыванию в Delphi

Delphi , Синтаксис , Сортировка

Быстрая сортировка (QuickSort) — это эффективный алгоритм сортировки, который использует разделение на части для упрощения процесса сортировки. В языке программирования Delphi, который использует Object Pascal, реализация QuickSort может быть полезной для работы со списками и массивами.

Проблема реализации порядка сортировки

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

Решение: изменение порядка сравнения

Чтобы изменить порядок сортировки, необходимо изменить порядок сравнения элементов. В коде QuickSort есть два цикла, которые отвечают за перестановку элементов относительно опорного элемента (pivot):

while List[Lo] < Mid do Inc(Lo);
while List[Hi] > Mid do Dec(Hi);

Для сортировки по убыванию необходимо изменить эти строки на следующие:

while List[Lo] > Mid do Inc(Lo);
while List[Hi] < Mid do Dec(Hi);

Таким образом, меняя направление сравнения, можно легко переключаться между сортировкой по возрастанию и убыванию.

Альтернативный ответ: использование обобщенных функций сортировки

В комментариях к вопросу указывается, что использование отдельных функций для сортировки по возрастанию и убыванию может быть избыточным. Предлагается использовать обобщенную функцию сортировки, такую как System.Generics.Collections.TArray.Sort, которая позволяет сортировать различные типы данных без необходимости написания новых функций сортировки для каждого из них.

Подтвержденный ответ и выводы

Используя QuickSort в Delphi, можно эффективно сортировать данные, изменяя порядок сравнения элементов для переключения между сортировкой по возрастанию и убыванию. Это простой и эффективный способ реализации требуемой функциональности без необходимости создания дополнительных функций сортировки.

Пример кода на Object Pascal для QuickSort, который позволяет переключать порядок сортировки, выглядит следующим образом:

procedure QuickSort(var List: TArrayOfMyType; Lo, Hi: Integer; Ascending: Boolean);
var
  Mid: Integer;
begin
  if Lo < Hi then
  begin
    Mid := Partition(List, Lo, Hi, Ascending);
    QuickSort(List, Lo, Mid - 1, Ascending);
    QuickSort(List, Mid + 1, Hi, Ascending);
  end;
end;

function Partition(var List: TArrayOfMyType; Lo, Hi: Integer; Ascending: Boolean): Integer;
var
  MidValue, Temp: TMyType;
  LoIndex, HiIndex: Integer;
begin
  MidValue := List[Lo];
  LoIndex := Lo + 1;
  HiIndex := Hi;
  while True do
  begin
    while (Ascending and List[LoIndex] <= MidValue) or
           (not Ascending and List[LoIndex] >= MidValue) do
      Inc(LoIndex);
    while (Ascending and List[HiIndex] >= MidValue) or
           (not Ascending and List[HiIndex] <= MidValue) do
      Dec(HiIndex);
    if LoIndex >= HiIndex: break;
    Temp := List[LoIndex];
    List[LoIndex] := List[HiIndex];
    List[HiIndex] := Temp;
    Inc(LoIndex);
    Dec(HiIndex);
  end;
  Temp := List[Lo];
  List[Lo] := List[HiIndex];
  List[HiIndex] := Temp;
  Result := HiIndex;
end;

Этот код позволяет вызывать функцию сортировки с указанием направления сортировки через параметр Ascending. Если Ascending истинно, сортировка будет выполнена по возрастанию, если ложно — по убыванию.

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

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

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

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

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