Простой способ добавить стабильную сортировку в TList и TStringList

Question

Я использую TList / TObjectList и TStringList (со связанными объектами) для множества задач, как есть, или в качестве основы для более сложных структур. Хотя функции сортировки обычно достаточно хороши, мне иногда нужно выполнить сортировку stable , и в обоих списках используется быстрая сортировка.

Какой самый простой способ реализовать стабильную сортировку для TList и / или TStringList? Нужно ли мне писать свою собственную процедуру сортировки или это можно сделать с помощью некоторого умного трюка с TStringListSortCompare / TListSortCompare?

Answer 1

Вам придется написать собственную процедуру сортировки.

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

Некоторые хитрости:

• Если вы уверены, что индекс <<code>Count, вы можете использовать массив быстрых указателей (TList.List[]) вместо более медленных Items[] или GetItem(): вызов под-метода и проверка диапазона замедляют выполнение ;
• Функция сравнения в большинстве случаев является узким местом в скорости поиска, поэтому позаботьтесь об этой части;
• Если вам нужна скорость, используйте реальный профилировщик над реальными (например, случайными) данными - но сделайте это правильно, прежде чем делать это быстро;
• Начать с существующей реализации сортировки;
• Чтобы минимизировать пространство стека, вы можете использовать временную запись для хранения и совместного использования переменных среди рекурсивных вызовов.

Answer 2

Этот вопрос довольно старый, но вот мой ответ для будущих читателей: он мне тоже недавно понадобился, и я адаптировал реализацию, найденную в книге «Томы алгоритмов Дельфи и структуры данных» Джулиана Бакнолла.Реализация для классов TList, TObjectList и потомков.Он работает с Delphi 2009 до XE7 и, возможно, с другими версиями: http://alexandrecmachado.blogspot.com.br/2015/02/merge-sort-for-delphi.html

Answer 3

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

uses Generics.Defaults, Generics.Collections;

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

implementation

class procedure TMySort.InsertionSort<T>(AArray: TArray<T>; FirstIndex, LastIndex: Integer; const AComparer: IComparer<T>);
var
  UnsortedIdx, CompareIdx: Integer;
  AItem: T;
begin
  for UnsortedIdx := Succ(FirstIndex) to LastIndex do begin
    AItem := AArray[UnsortedIdx];
    CompareIdx := UnsortedIdx - 1;
    while (CompareIdx >= FirstIndex) and (AComparer.Compare(AItem, AArray[CompareIdx]) < 0) do begin
      AArray[CompareIdx + 1] := AArray[CompareIdx]; { shift the compared (bigger) item to the right }
      Dec(CompareIdx);
    end;
    AArray[CompareIdx + 1] := AItem;
  end;
end;

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
    { sort small chunks with insertion sort (recursion ends here)}
    TMySort.InsertionSort<T>(AArray, FirstIndex, LastIndex, AComparer)
  else begin
    { MERGE SORT }
    { calculate the index for splitting the array in left and right halves }
    LeftLast := (FirstIndex + LastIndex) div 2;
    RightFirst := LeftLast + 1;
    { sort both halves of the array recursively }
    TMySort.MergeSort<T>(AArray, FirstIndex, LeftLast, AComparer);
    TMySort.MergeSort<T>(AArray, RightFirst, LastIndex, AComparer);
    { copy the first half of the array to a temporary array }
    LeftCount := LeftLast - FirstIndex + 1;
    TmpLeftArray := System.Copy(AArray, FirstIndex, LeftCount);
    { setup the loop variables }
    LeftIdx := 0;  { left array to merge -> moved to TmpLeftArray, starts at index 0 }
    RightIdx := RightFirst; { right array to merge -> second half of AArray }
    SortedIdx := FirstIndex - 1; { range of merged items }
    { merge item by item until one of the arrays is empty }
    while (LeftIdx < LeftCount) and (RightIdx <= LastIndex) do begin
      { get the smaller item from the next items in both arrays and move it
        each step will increase the sorted range by 1 and decrease the items still to merge by 1}
      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;
    { copy the rest of the left array, if there is any}
    while (LeftIdx < LeftCount) do begin
      Inc(SortedIdx);
      AArray[SortedIdx] := TmpLeftArray[LeftIdx];
      Inc(LeftIdx);
    end;
    { any rest of the right array is already in place }
  end;
end;

Реализация сделана для массивов и применима также для TList / TObjectList (так как их свойство Items является массивом).

var
  AList: TList<T>;
  AComparer: IComparer<T>;
begin
  ...
  TMySort.MergeSort<T>(AList.List, 0, AList.Count-1, AComparer);
  ...
end;

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

Answer 4

Из аналогичного вопроса Как я могу заменить StringList.Sort на Стабильную сортировку в Delphi? , связанный здесь в комментарии lkessler. Мне нужно скопировать здесь очень простой трюк, как упоминалось в вопросе.

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

Легко, быстро и умно. Стоит только одно дополнительное целое число (или байт, или использовать зарезервированное хранилище, например TComponent.Tag, если вы сортируете TComponents) для каждого сортируемого элемента и один цикл инициализации над ними.

TObjectToSort = class
  ...
  Index: Integer;
end;

function MyStableSortComparer(List: TStringList; Index1, Index2: Integer): Integer;
var
  o1, o2: TObjectToSort; 
begin
  o1 := TObjectToSort(List.Objects[Index1]);
  o2 := TObjectToSort(List.Objects[Index2]);
  ...
  if Result = 0 then
    Result := o1.Index - o2.Index;
end;


for i := 0 to MyStrtingList.Count - 1 do
  TObjectToSort(MyStrtingList.Objects[i]).Index := i;
MyStrtingList.CustomSort(MyStableSortComparer);