Sorting dynamic Array of Array of Double in Delphi

Question

I create a dynamic matrix in Delphi:

AMatrix : Array of Array of Double;

and let's suppose that I initialize it this way.

SetLength(Amatrix,1000,10);

And fill this matrix using some values. Now, I want to sort the 1000 items on the first dimension on a specific value stored in a specific position on the second dimension (from 0 to 9).

Is there a way to create a TComparer that can be applied directly on the Amatrix without the need to create other data structures (TList or TArray)?

Answer 1

Is there a way to create a TComparer<T> that can be applied directly on [a variable of type array of array of Double] without the need to create other data structures (TList or TArray)?

Let's try it, but we'll use integers for simplicity:

program FailedAttempt;

{$APPTYPE CONSOLE}

{$R *.res}

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

var
  A: array of array of Integer;

begin

  A :=
    [
      [5, 2, 1, 3, 6],
      [1, 2, 6, 3, 2],
      [1, 6, 7, 8, 3],
      [5, 7, 4, 2, 1],
      [0, 4, 9, 0, 5],
      [4, 1, 8, 9, 6]
    ];

  TArray.Sort<array of Integer>(A,
    TComparer<array of Integer>.Construct(
      function(const Left, Right: array of Integer): Integer
      begin
        if Left[2] < Right[2] then
          Result := -1
        else if Left[2] > Right[2] then
          Result := +1
        else
          Result := 0;
      end
    )
  );

  for var i := 0 to High(A) do
  begin
    Writeln;
    for var j := 0 to High(A[i]) do
      Write(A[i, j]);
  end;

  Readln;

end.

Unfortunately, this won't compile, since array of Integer isn't a valid type you can use as T. Notice how this is just like how you cannot use array of Integer as the return type of a function. And the solution is the same, too: Create a type defined as array of Integer.

program Solution1;

{$APPTYPE CONSOLE}

{$R *.res}

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

type
  TIntArray = array of Integer;

var
  A: array of TIntArray;

begin

  A :=
    [
      [5, 2, 1, 3, 6],
      [1, 2, 6, 3, 2],
      [1, 6, 7, 8, 3],
      [5, 7, 4, 2, 1],
      [0, 4, 9, 0, 5],
      [4, 1, 8, 9, 6]
    ];

  TArray.Sort<TIntArray>(A,
    TComparer<TIntArray>.Construct(
      function(const Left, Right: TIntArray): Integer
      begin
        if Left[2] < Right[2] then
          Result := -1
        else if Left[2] > Right[2] then
          Result := +1
        else
          Result := 0;
      end
    )
  );

  for var i := 0 to High(A) do
  begin
    Writeln;
    for var j := 0 to High(A[i]) do
      Write(A[i, j]);
  end;

  Readln;

end.

But in modern versions of Delphi, you don't need to create your own type (and, indeed, that is a bad idea, since different such types are not compatible). Instead, just use TArray<Integer> which is indeed defined as array of Integer -- this is a dynamic array of integers, just like your array of Integer:

program Solution2;

{$APPTYPE CONSOLE}

{$R *.res}

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

var
  A: array of TArray<Integer>;

begin

  A :=
    [
      [5, 2, 1, 3, 6],
      [1, 2, 6, 3, 2],
      [1, 6, 7, 8, 3],
      [5, 7, 4, 2, 1],
      [0, 4, 9, 0, 5],
      [4, 1, 8, 9, 6]
    ];

  TArray.Sort<TArray<Integer>>(A,
    TComparer<TArray<Integer>>.Construct(
      function(const Left, Right: TArray<Integer>): Integer
      begin
        if Left[2] < Right[2] then
          Result := -1
        else if Left[2] > Right[2] then
          Result := +1
        else
          Result := 0;
      end
    )
  );

  for var i := 0 to High(A) do
  begin
    Writeln;
    for var j := 0 to High(A[i]) do
      Write(A[i, j]);
  end;

  Readln;

end.

If you really cannot change the definition of A, you can use casting:

program Solution3;

{$APPTYPE CONSOLE}

{$R *.res}

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

var
  A: array of array of Integer;

begin

  A :=
    [
      [5, 2, 1, 3, 6],
      [1, 2, 6, 3, 2],
      [1, 6, 7, 8, 3],
      [5, 7, 4, 2, 1],
      [0, 4, 9, 0, 5],
      [4, 1, 8, 9, 6]
    ];

  TArray.Sort<TArray<Integer>>(TArray<TArray<Integer>>(A),
    TComparer<TArray<Integer>>.Construct(
      function(const Left, Right: TArray<Integer>): Integer
      begin
        if Left[2] < Right[2] then
          Result := -1
        else if Left[2] > Right[2] then
          Result := +1
        else
          Result := 0;
      end
    )
  );

  for var i := 0 to High(A) do
  begin
    Writeln;
    for var j := 0 to High(A[i]) do
      Write(A[i, j]);
  end;

  Readln;

end.

Finally, I should also point out the obvious: it is possible to sort your data without using a TComparer<T>. (Indeed, you were forced to do so before generics were introduced in Delphi 2009.)

Answer 2

Using @R.Hoeck idea I wrote a simple demo program which create a two dimensions array of double, fill it with random data and sort it using a given column as key.

Sorting is done by creating a list of index/value for the column and then sorting the list.

After sorting, data from unsorted array is copied to another array which will become sorted.

unit MatrixDemoMain;

interface

uses
  Winapi.Windows, Winapi.Messages,
  System.SysUtils, System.Variants, System.Classes,
  Vcl.Graphics, Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls,
  System.Generics.Defaults,
  System.Generics.Collections;

type
    TMyRecord = record
        Index : Integer;
        Value : Double;
    end;
    TDynArray2OfDouble = array of array of Double;

    TForm1 = class(TForm)
        Button1: TButton;
        Memo1: TMemo;
        procedure Button1Click(Sender: TObject);
    private
        procedure DisplayArray(const Title : String;
                               const Arr   : TDynArray2OfDouble);
    end;

var
    Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
var
    AMatrix      : TDynArray2OfDouble;
    SortedMatrix : TDynArray2OfDouble;
    I, J         : Integer;
    SortCol      : Integer;
    Rec          : TMyRecord;
    List         : TList<TMyRecord>;
begin
    // Give dimension to unsorted array
    SetLength(AMatrix, 10, 3);
    // Give dimension to the sorted array
    SetLength(SortedMatrix, High(AMatrix) + 1, High(AMatrix[0]) + 1);
    // Select column to use as sort key
    SortCol := 2;

    // Fill matrix with random data
    for I := 0 to High(AMatrix) do begin
        for J := 0 to High(AMatrix[0]) do
            AMatrix[I, J] := Random(1000);
    end;
    DisplayArray('Unsorted:', AMatrix);

    // Create a list to sort data
    List := TList<TMyRecord>.Create;
    try
        for I := 0 to High(AMatrix) do begin
            Rec.Index := I;
            Rec.Value := AMatrix[I, SortCol];
            List.Add(Rec);
        end;
        // Sort the list
        List.Sort(TComparer<TMyRecord>.Construct(
                    function(const Left, Right: TMyRecord): Integer
                    begin
                        if Left.Value = Right.Value then
                            Result := 0
                        else if Left.Value > Right.Value then
                            Result := 1
                        else
                            Result := -1;
                    end)
                  );

        // Copy data from unsorted matrix using sorted list
        for I := 0 to High(AMatrix) do
            SortedMatrix[I] := AMatrix[List[I].Index];

        DisplayArray('Sorted on column ' + SortCol.ToString, SortedMatrix);
    finally
        FreeAndNil(List);
    end;
end;

// This procedure will display an array into the memo
procedure TForm1.DisplayArray(
    const Title : String;
    const Arr   : TDynArray2OfDouble);
var
    I, J    : Integer;
    Buf     : String;
begin
    Memo1.Lines.Add(Title);
    for I := 0 to High(Arr) do begin
        Buf := I.ToString + ') ';
        for J := 0 to High(Arr[0]) do
            Buf := Buf + Arr[I, J].ToString + '  ';
        Memo1.Lines.Add(Buf);
    end;
end;

end.

Running the demo will display this result in the memo:

Unsorted:
0) 293  547  16  
1) 238  503  543  
2) 428  950  663  
3) 150  444  739  
4) 160  388  373  
5) 945  382  417  
6) 863  818  392  
7) 344  131  617  
8) 91  458  330  
9) 370  717  191  
Sorted on column 2
0) 293  547  16  
1) 370  717  191  
2) 91  458  330  
3) 160  388  373  
4) 863  818  392  
5) 945  382  417  
6) 238  503  543  
7) 344  131  617  
8) 428  950  663  
9) 150  444  739