Sort arrays by multiple fields

Question

I have multiple arrays and they all start with integer fields, from 1 up to 5 fields, and these are like indexes that need to be sorted, from min to max:

    TArrayA = record
          Field1:integer;
          Field2:integer;
          Field3:integer;
          Field4:integer;
          Field5:integer;
          ... //other fields, strings, integers... up to 50 fields
        end;

    ArrayA:=array of TArrrayA;

Currently I use this approach to sort:

    // sort by Field1
    top:=Length(ArrayA);
      for counter := 0 to top do
        begin
          min := counter;
          for look := counter + 1 to top do
            if ArrayA[look].Field1 < ArrayA[min].Field1 then
              min := look;
          vTmpRecord := ArrayA[min];
          ArrayA[min] := ArrayA[counter];
          ArrayA[counter] := vTmpRecord;
        end;

   // now sort by Field2
    top:=Length(ArrayA);
      for counter := 0 to top do
        begin
          min := counter;
          for look := counter + 1 to top do
            if (ArrayA[look].Field1 = ArrayA[min].Field1) And 
               (ArrayA[look].Field2 < ArrayA[min].Field2) then
              min := look;
          vTmpRecord := ArrayA[min];
          ArrayA[min] := ArrayA[counter];
          ArrayA[counter] := vTmpRecord;
        end;

This does the job. Although is a bit slow when I need to sort all 5 fields, and this is how I do it, field by field, so I sort the array 5 times. Is there any better, faster way?

Here is example:

procedure TForm1.Button8Click(Sender: TObject);
type
  TArrayA = record
    Field1: integer;
    Field2: integer;
    Field3: integer;
    Field4: integer;
    Field5: integer;
  end;
var
  ArrayA: array of TArrayA;
  vTmpRecord: TArrayA;
  top, counter, min, max, look: integer;
  i,t1,t2:integer;
begin

  SetLength(ArrayA,100000);
  for i := 0 to 99999 do
  begin
    ArrayA[i].Field1:=1+Random(100);
    ArrayA[i].Field2:=1+Random(100);
    ArrayA[i].Field3:=1+Random(100);
    ArrayA[i].Field4:=1+Random(100);
    ArrayA[i].Field5:=1+Random(100);
  end;


  t1:=GetTickCount;
  // sort by Field1
  top := Length(ArrayA);
  for counter := 0 to top do
  begin
    min := counter;
    for look := counter + 1 to top do
      if ArrayA[look].Field1 < ArrayA[min].Field1 then
        min := look;
    vTmpRecord := ArrayA[min];
    ArrayA[min] := ArrayA[counter];
    ArrayA[counter] := vTmpRecord;
  end;

  // sort by Field2
  top := Length(ArrayA);
  for counter := 0 to top do
  begin
    min := counter;
    for look := counter + 1 to top do
      if (ArrayA[look].Field1 = ArrayA[min].Field1) and
        (ArrayA[look].Field2 < ArrayA[min].Field2) then
        min := look;
    vTmpRecord := ArrayA[min];
    ArrayA[min] := ArrayA[counter];
    ArrayA[counter] := vTmpRecord;
  end;

  // sort by Field3
  top := Length(ArrayA);
  for counter := 0 to top do
  begin
    min := counter;
    for look := counter + 1 to top do
      if (ArrayA[look].Field1 = ArrayA[min].Field1) and (ArrayA[look].Field2 = ArrayA[min].Field2) and
        (ArrayA[look].Field3 < ArrayA[min].Field3) then
        min := look;
    vTmpRecord := ArrayA[min];
    ArrayA[min] := ArrayA[counter];
    ArrayA[counter] := vTmpRecord;
  end;

  // sort by Field4
  top := Length(ArrayA);
  for counter := 0 to top do
  begin
    min := counter;
    for look := counter + 1 to top do
      if (ArrayA[look].Field1 = ArrayA[min].Field1) and (ArrayA[look].Field2 = ArrayA[min].Field2) and (ArrayA[look].Field3 = ArrayA[min].Field3) and
        (ArrayA[look].Field4 < ArrayA[min].Field4) then
        min := look;
    vTmpRecord := ArrayA[min];
    ArrayA[min] := ArrayA[counter];
    ArrayA[counter] := vTmpRecord;
  end;

  // sort by Field5
  top := Length(ArrayA);
  for counter := 0 to top do
  begin
    min := counter;
    for look := counter + 1 to top do
      if (ArrayA[look].Field1 = ArrayA[min].Field1) and (ArrayA[look].Field2 = ArrayA[min].Field2) and (ArrayA[look].Field3 = ArrayA[min].Field3) and (ArrayA[look].Field4 = ArrayA[min].Field4) and
        (ArrayA[look].Field5 < ArrayA[min].Field5) then
        min := look;
    vTmpRecord := ArrayA[min];
    ArrayA[min] := ArrayA[counter];
    ArrayA[counter] := vTmpRecord;
  end;

  t2:=GetTickCount;
  Button8.Caption:=IntToStr(t2-t1);
end;

See also: How to make an Excel-Like Sort By A, Then By B in a TObjectList<> using multiple comparers. — Rob Kennedy
– Rob Kennedy, Commented Nov 9, 2015 at 5:21

Dalija Prasnikar · Accepted Answer · 2015-11-08 15:04:56Z

4

You can use built in Quick sort method for sorting arrays with your custom comparer:

uses
  System.Math,
  System.Generics.Defaults,
  System.Generics.Collections;

  TArray.Sort<TArrayA>(ArrayA, TComparer<TArrayA>.Construct( function(const Left, Right: TArrayA): Integer
  begin
    if Left.Field1 = Right.Field1 then
      begin
        if Left.Field2 = Right.Field2 then
          begin
            Result := CompareValue(Left.Field3, Right.Field3);
          end
        else Result := CompareValue(Left.Field2, Right.Field2);
      end
    else Result := CompareValue(Left.Field1, Right.Field1);
  end
  ));

I added code only for first three fields, but you will get the picture how to build your own comparer for more fields.

edited Nov 8, 2015 at 15:04

answered Nov 8, 2015 at 13:56

Dalija Prasnikar♦

28.7k46 gold badges97 silver badges179 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Mike Torrettinni Over a year ago

This looks pretty easy and it seems to be extremely fast, from 60s down to 110 ms... am I missing something here? Why is this so fast and is there a case where this is not going to work?

David Heffernan Over a year ago

Read about quicksort and bubblesort, and their asymptotic behaviour. Do try to avoid using the comparer as implemented here since it is so full of repetition. Opt for a comparer that uses iteration.

Dalija Prasnikar Over a year ago

@DavidHeffernan Agreed, comparer here is repetitive. But, I think it paints the picture how you can build your own comparer well. Especially, if you have to use different comparing algorithms for different fields (which is not the case in this example code, of course)

David Heffernan Over a year ago

Comparers written like this are very hard to read. I do not commend an approach such as the code in your answer.

David Heffernan Over a year ago

At the very least you should use early return to avoid deep nested indentation, and avoid using subtraction which is susceptible to arithmetic overflow. But iteration is just much better. Don't repeat yourself.

|

David Heffernan · Accepted Answer · 2015-11-08 18:34:14Z

2

The most important thing for you to do is to separate the sort algorithm from the data. That way you can write, or use, a single sort algorithm again and again with different data

The classic way to do that is to use a comparison sort. They are sort algorithms that require a compare function that compares two items and returns a negative integer for less than, a positive integer for greater than, and zero when equal.

So, let's start by demonstrating such a compare function for your data. Storing multiple fields as you have makes it hard to write a general purpose comparer. Better to put the fields in an array. Once you have done so you can do the compare lexicographically using iteration like this:

function CompareIntegerArray(const lhs, rhs: array of Integer): Integer;
var
  i: Integer;
begin
  Assert(Length(lhs) = Length(rhs));
  for i := low(lhs) to high(lhs) do
    if lhs[i] < rhs[i] then
      exit(-1)
    else if lhs[i] > rhs[i] then
      exit(1);

  exit(0);
end;

With a lexicographic order we first compare the primary field. If they differ we have our answer, otherwise we move on to the secondary field. And so on. Such an algorithm is well suited to iteration as demonstrated above.

This overcomes a significant weakness in your approach, by sorting the array once only.

Once you have this compare function you need to wrap it in an outer compare function that extracts data from the record fields and populates arrays. Perhaps along these lines:

type
  TMyArray = array [1..5] of Integer;

function GetMyArray(const Value: TArrayA): TMyArray;
begin
  Result[1] := Value.Field1;
  Result[2] := Value.Field2;
  ....
end;

function MyCompare(const lhs, rhs: TArrayA): Integer;
begin
  Result := CompareIntegerArray(
    GetMyArray(lhs),
    GetMyArray(rhs)
  );
end;

Now, as promised, you can use this compare function with a general purpose sort like TArray.Sort<T> from Generics.Collections. This is an implementation of Quicksort, a comparison sort with average complexity of O(n log n). That will typically yield a huge benefit over your O(n²) bubble sort.

Life would be simpler if you could replace the record with an actual array. Another option that might be useful would be to add a method to the record that returned an array of integer ready for use in the lexicographic compare function.

To recap:

Separate data, comparison and sorting to facilitate re-use and clarity.
Use arrays to enable lexicographic compare to be implemented with a loop.
Use an efficient sort algorithm such as Quicksort.

edited Nov 8, 2015 at 18:34

answered Nov 8, 2015 at 14:22

David Heffernan

616k46 gold badges1.1k silver badges1.5k bronze badges

3 Comments

Mike Torrettinni Over a year ago

your suggestion is interesting and it seems like it is working. So, I just set it like this and it works:

TArray.Sort<TArrayA>(ArrayA, TComparer<TArrayA>.Construct( function(const Left, Right: TArrayA): Integer   begin     Result:=MyCompare(Left,Right);   end   ));

. And if I want to sort different array, like array of TArrayA2, I just simply copy function GetMyArrayA2(const Value: TArrayA2): TMyArray; and function MyCompareA2(const lhs, rhs: TArrayA2): Integer; and call this new MyCompareA2 in TArray.Sort, correct? Your example is little slower than Dalija's, around 170ms vs 120ms.

David Heffernan Over a year ago

You've got a needless extra layer of indirection in the comparer. You can pass MyCompare directly to Construct. Or you can move the body of MyCompare into an anon method that you pass to Construct. I was more interested in getting across concepts than optimising perf.

Mike Torrettinni Over a year ago

Thank you, it seems to be the solution i can apply throughout my application - around 150 sorting sections.

Collectives™ on Stack Overflow

Sort arrays by multiple fields

2 Answers 2

9 Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

9 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related