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;

Answer 1

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:

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

Answer 2

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.