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.