Best way to keep an array sorted when adding/deleting cells

Question

Version of Delphi used: 2007

Hello,

I have an array of Tecord

TInfo = Record
 Name : String;
 Price : Integer;
end;

var Infos : Array of Tinfo;

I was looking for a way to sort my Infos array and found what I thought to be a clever way to do it. Basically, I have a TList in which I add the pointers to each cell of the array; and then, I sort them using a custom sorting function. This TList is then used to show sorted cells in a TListView with OwnerData set to true.

var SortedInfo : TList;

...

function CompareInfo(Item1, Item2: Integer): Integer;
var
 i, j : integer;
begin
 i := Integer(Item1);
 j := Integer(Item2);
 Result := CompareText(Infos[i].Name, Infos[j].Name);
end;

...

for I := 0 to Length(Infos) - 1 do SortedInfo.Add(Pointer(I));
SortedInfo.Sort(@CompareInfo);

...

procedure InfoHandlerData(Sender: TObject; Item: TListItem);
begin
 Item.Caption := Infos[Integer(SortedInfo[Item.Index])].Name;
 Item.SubItems.Add(IntToStr(Infos[Integer(SortedInfo[Item.Index])].Price);
end;

Now, I want to be able to add and delete cells while keeping my pointers sorted. Now, here are my problems.

1. When I add a cell, I have to resort the whole list of pointers by calling SortedInfo.Sort(@CompareInfo);
2. When I delete a cell, I have to clean my TList, rebuild the list of pointers and sort them again.

Now, I don't have a huge number of cells, so there is no performance problem. However, rebuilding pointers when I delete a cell and sorting all the pointers each time the array changes seem wrong to me. I'm sorry if my problem seems stupid, but I'm trying to learn.

Is there a right way to keep my array sorted? I'm not sure how I'm supposed to "individually" sort new cells or how I'm supposed to keep the pointers valid when a cell is deleted...

Answer 1

There are two ways to handle this, depending on usage. But first, you should probably be using a TList instead of an array. It has methods for handling insertions and deletions and keeping things in order.

If you're performing a lot of inserts at a time, you'll want to use the dirty insert algorithm, which works like this:

The list comes with an associated flag, a boolean value called Dirty. When you insert something, stick it on the end of the list, and set Dirty to True. When you go to read from the list, first check the Dirty flag, and if its value is True, sort the list, set Dirty := False; and then do the read. With a lot of inserts, this is much faster than keeping the list in sorted order as you insert.

However, if you're not likely to be doing several inserts at a time, it's cheaper to maintain the list in sorted order. You don't need to do that by calling Sort every time, though. You do it like this:

Because your data is already sorted, you can find the correct position for a new value by using a binary search. Have the Insert operation use a binary search to determine where the new value should go, insert it there, and your list remains in sorted order.

As for deletes, you shouldn't have to worry about sorting order. Just call Delete on your TList, and if it started out sorted, removing an item won't change that.

Answer 2

Using both a dynamic array and a TList is not good. Use one or other, but not both. Inserting is easy in TList, but you need to manage lifetime of your pointers. You are looking at heap allocation. For a dynamic array, lifetime is easy, but insertion and deletion requires a bit of care. Of course, if you had modern Delphi it would be trivial with TList.

Use insertion sort to maintain the ordering of your array. Whenever you insert a new item, insert it at a position where it is greater than the previous element, and less than the subsequent element. If your list is already ordered, then inserting following this rule maintains the ordered property. For efficiency you can use binary search to find the insertion point. For an example of this look at TStringList when Sorted is True.

Before you tackle binary search (surprisingly tricky to get right), implement a version with linear search. Prove to yourself this works, and then move on to binary search if you need the extra efficiency.

When deleting, simply delete the item. Deleting any item from an ordered array preserves the ordered property.

Your compare function is a little "odd". All you need is:

function CompareInfo(Item1, Item2: Integer): Integer;
begin
  Result := CompareText(Infos[Item1].Name, Infos[Item2].Name);
end;

Answer 3

Well, if you want to maintain a list of ordered names along with its data use TStringList instead of TList. Use its Objects attributes to keep the record reference.

It does the sort for you whether you insert or delete items. For example:

Var
   List:TStringList;
begin
   List:=TStringList.Create();
   List.Sorted:=True;
   // depending on your duplicates records use one of the following:
   List.Duplicates:=[dupIgnore, dupAccept, dupError];

   // You add record to the list this way:
   List.AddObject(RecPtr^.name, TObject(RecPtr));
   // or
   List.AddObject(MyRecord.name, TObject(@MyRecord));
   // When you want to access the record from an item, typecast it
   with TMyRecordType(List.Objects[IndexToTheObject])^ do
   begin
   end;

   // To delete an item:
   List.Delete(Index);

   // To find a specific record:
   Index:=List.IndexOf(MyNameSearch);
end;