Реализация стабильной сортировки в TList и TStringList: альтернатива быстрой сортировке

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

При работе с TList и TStringList в Delphi часто требуется выполнить стабильную сортировку, но по умолчанию они используют быструю сортировку (quicksort), которая не является стабильной. В этой статье мы рассмотрим несколько способов реализовать стабильную сортировку для этих коллекций.

Почему быстрая сортировка не стабильна?

Быстрая сортировка работает путем выбора опорного элемента и разделения других элементов на две подгруппы: элементы, которые меньше опорного, и элементы, которые больше. Затем сортировка рекурсивно применяется к каждой подгруппе. Хотя этот алгоритм является одним из самых быстрых в среднем случае, он не является стабильным, то есть элементы с одинаковыми ключами сортировки могут менять свой порядок после сортировки.

Реализация стабильной сортировки

Существует несколько способов реализовать стабильную сортировку для TList и TStringList. Рассмотрим два основных подхода:

1. Использование встроенных функций сравнения и настройка сортировки Одним из простых способов реализовать стабильную сортировку является использование встроенных функций сравнения TStringListSortCompare и TListSortCompare, а также настройка сортировки на стабильную. Для этого нужно переопределить функцию сравнения и добавить проверку на равенство ключей сортировки.

Вот пример переопределения функции сравнения для TStringList:

type
  TCustomStringList = class(TStringList)
  protected
    function Compare(S1, S2: string): Integer; override;
  end;

{ TCustomStringList }

function TCustomStringList.Compare(S1, S2: string): Integer;
begin
  Result := S1.CompareTo(S2);
  if Result = 0 then
    Result := -1; { или 1, в зависимости от того, хотите ли вы сохранить исходный порядок или нет }
end;

После этого можно использовать стабильную сортировку с помощью TStringList.Sort:

var
  MyStringList: TCustomStringList;
begin
  MyStringList := TCustomStringList.Create;
  try
    MyStringList.Sort;
  finally
    MyStringList.Free;
  end;
end;

Аналогичным образом можно переопределить функцию сравнения для TList, используя TListSortCompare.

1. Использование другого стабильного алгоритма сортировки Другой подход заключается в использовании другого стабильного алгоритма сортировки, такого как сортировка слиянием или сортировка вставками. Для этого можно написать собственную функцию сортировки или использовать готовую реализацию, например, из пакета Generics.Collections.

Вот пример реализации стабильной сортировки слиянием для TList:

uses
  Generics.Collections;

type
  TMySort = class
  public
    class procedure MergeSort<T>(AArray: TArray<T>; FirstIndex, LastIndex: Integer; const AComparer: IComparer<T>); static;
  end;

{ TMySort }

class procedure TMySort.MergeSort<T>(AArray: TArray<T>; FirstIndex, LastIndex: Integer; const AComparer: IComparer<T>);
const
  MinMergeSortLimit = 16;
var
  LeftLast, RightFirst: Integer;
  LeftIdx, RightIdx, SortedIdx: Integer;
  LeftCount: Integer;
  TmpLeftArray: TArray<T>;
begin
  if (LastIndex - FirstIndex) < MinMergeSortLimit then
    // сортировка небольших массивов с помощью сортировки вставками
    TMySort.InsertionSort<T>(AArray, FirstIndex, LastIndex, AComparer)
  else begin
    // сортировка слиянием
    LeftLast := (FirstIndex + LastIndex) div 2;
    RightFirst := LeftLast + 1;
    TMySort.MergeSort<T>(AArray, FirstIndex, LeftLast, AComparer);
    TMySort.MergeSort<T>(AArray, RightFirst, LastIndex, AComparer);
    LeftCount := LeftLast - FirstIndex + 1;
    TmpLeftArray := System.Copy(AArray, FirstIndex, LeftCount);
    LeftIdx := 0; { левый массив для слияния -&gt; перемещен в TmpLeftArray, начинается с индекса 0 }
    RightIdx := RightFirst; { правый массив для слияния -&gt; вторая половина AArray }
    SortedIdx := FirstIndex - 1; { диапазон отсортированных элементов }
    while (LeftIdx < LeftCount) and (RightIdx <= LastIndex) do begin
      Inc(SortedIdx);
      if AComparer.Compare(TmpLeftArray[LeftIdx], AArray[RightIdx]) <= 0 then begin
        AArray[SortedIdx] := TmpLeftArray[LeftIdx];
        Inc(LeftIdx);
      end else begin
        AArray[SortedIdx] := AArray[RightIdx];
        Inc(RightIdx);
      end;
    end;
    while (LeftIdx < LeftCount) do begin
      Inc(SortedIdx);
      AArray[SortedIdx] := TmpLeftArray[LeftIdx];
      Inc(LeftIdx);
    end;
  end;
end;

После этого можно использовать эту функцию для сортировки TList:

var
  MyList: TList<Integer>;
  AComparer: IComparer<Integer>;
begin
  MyList := TList<Integer>.Create;
  try
    AComparer := TComparer<Integer>.Create;
    try
      TMySort.MergeSort<Integer>(MyList.List, 0, MyList.Count - 1, AComparer);
    finally
      AComparer.Free;
    end;
  finally
    MyList.Free;
  end;
end;

Вывод

Реализовать стабильную сортировку для TList и TStringList можно несколькими способами: переопределив встроенные функции сравнения или используя другой стабильный алгоритм сортировки. Выбор подхода зависит от конкретных требований к производительности и удобству использования.

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

Данный контекст посвящен альтернативным способам реализации стабильной сортировки для TList и TStringList в Delphi, так как по умолчанию они используют нестабильный алгоритм быстрой сортировки (quicksort).

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

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

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