"Фиксированная сортировка объектов в Delphi и Pascal"

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

В современных приложениях на Delphi и Pascal часто возникает потребность в сортировке коллекций объектов. Однако, встроенные функции сортировки, такие как Sort для TObjectList<T>, могут приводить к неожиданным результатам, когда объекты имеют равные значения по критерию сортировки. В этой статье мы рассмотрим проблему, связанную со сменой позиций равных значений при сортировке, и предложим решение, которое гарантирует фиксированный порядок для равных значений.

Проблема

Рассмотрим следующий пример кода, где мы создаем список объектов TMyObject и сортируем его по значению свойства DoubleValue:

type
  TMyObject = class
  private
    FDoubleValue: Double;
    FText: string;
  public
    constructor Create(ADoubleValue: Double; AText: string);
    property DoubleValue: Double read FDoubleValue write FDoubleValue;
    property Text: string read FText write FText;
  end;

procedure TForm1.FormCreate(Sender: TObject);
var
  MyObjects: TObjectList<TMyObject>;
  i: Integer;
begin
  MyObjects := TObjectList<TMyObject>.Create;
  MyObjects.OwnsObjects := True;

  MyObjects.Add(TMyObject.Create(100.00, 'Item 1'));
  MyObjects.Add(TMyObject.Create(200.00, 'Item 2'));
  MyObjects.Add(TMyObject.Create(300.00, 'Item 3')); // Duplicate sort value
  MyObjects.Add(TMyObject.Create(300.00, 'Item 4')); // Duplicate sort value
  MyObjects.Add(TMyObject.Create(400.00, 'Item 5'));

  // Сортировка списка по свойству DoubleValue
  MyObjects.Sort(TComparer<TMyObject>.Construct(
    function(const A, B: TMyObject): Integer
    begin
      Result := CompareValue(A.DoubleValue, B.DoubleValue, 0);
    end));

  // Вывод отсортированного списка в ListBox1
  for i := 0 to MyObjects.Count - 1 do
    ListBox1.Items.Add(Format('%d - %.1f - %s', [i, MyObjects[i].DoubleValue, MyObjects[i].Text]));
end;

При запуске данного кода мы можем заметить, что объекты с одинаковыми значениями свойства DoubleValue меняют свою позицию в списке после сортировки. Это происходит из-за того, что встроенная функция сортировки Sort использует нестабильный алгоритм сортировки (Quicksort), который не гарантирует сохранение исходного порядка для равных значений.

Решение

Чтобы гарантировать фиксированный порядок для равных значений при сортировке, мы можем использовать стабильный алгоритм сортировки, такой как TimSort. Библиотека Spring4D предоставляет стабильную версию функции сортировки StableSort, которую мы можем использовать для решения нашей проблемы.

Сначала необходимо добавить библиотеку Spring4D в наш проект. После этого мы можем изменить нашу функцию сортировки следующим образом:

uses
  ..., Spring4D.SysUtils, Spring4D.Collections;

procedure TForm1.FormCreate(Sender: TObject);
begin
  // ... (создание списка MyObjects)

  // Сортировка списка по свойству DoubleValue с использованием стабильного алгоритма
  TStableSort<TMyObject>.Sort(MyObjects, TComparer<TMyObject>.Construct(
    function(const A, B: TMyObject): Integer
    begin
      Result := CompareValue(A.DoubleValue, B.DoubleValue, 0);
    end));

  // ... (вывод отсортированного списка в ListBox1)
end;

Теперь, при сортировке списка объектов TMyObject по значению свойства DoubleValue, объекты с одинаковыми значениями сохранят свой исходный порядок. Это гарантирует фиксированную сортировку и предотвращает нежелательную смену позиций равных значений.

Альтернативное решение

Если по какой-то причине вы не можете или не хотите использовать библиотеку Spring4D, вы можете написать собственный стабильный алгоритм сортировки или использовать встроенную функцию сортировки Sort с расширенным сравнителем, который учитывает дополнительные критерии сортировки для равных значений. Например, мы можем добавить сравнение по свойству Text в нашем примере:

procedure TForm1.FormCreate(Sender: TObject);
begin
  // ... (создание списка MyObjects)

  // Сортировка списка по свойству DoubleValue с расширенным сравнителем
  MyObjects.Sort(TComparer<TMyObject>.Construct(
    function(const A, B: TMyObject): Integer
    begin
      if CompareValue(A.DoubleValue, B.DoubleValue, 0) = 0 then
        Result := CompareText(A.Text, B.Text)
      else
        Result := CompareValue(A.DoubleValue, B.DoubleValue, 0);
    end));

  // ... (вывод отсортированного списка в ListBox1)
end;

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

Заключение

В этой статье мы рассмотрели проблему нестабильной сортировки равных значений в Delphi и Pascal и предложили два решения: использование стабильного алгоритма сортировки из библиотеки Spring4D или расширение сравнителя для учета дополнительных критериев сортировки. Выбор решения зависит от конкретных требований вашего проекта и возможностей, доступных в вашей текущей среде разработки.

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

В современных приложениях на Delphi и Pascal при сортировке коллекций объектов встроенные функции сортировки могут приводить к неожиданным результатам, когда объекты имеют равные значения по критерию сортировки, меняя позицию равных значений. В статье рас

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

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

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