CODEWITHSUNDEEP
arraysdelphisorting
Bjarke Moholt
Bjarke Moholt

Reputation: 323

sorting an Array and get the indexes in Delphi

I have a small puzzle that's giving me headaches and should be quite enjoyable to solve.

I have a set of arrays

arrayX : array of real;
arrayY : array of real;

that represent a number of points x,y such that ( arrayX[0], arrayY[0] ) constitutes a point. Now, I want to sort these arrays with respect to X and I'm thinking the way must be to get a list of sorted indexes by arrayX and apply this to both arrays, and here my problem arises:

How to write a function that gives me the sorted indexes (ascending) of arrayX, preferably in an array of integers? ArrayX can hold duplicate values

Upvotes: 1

Views: 1724

Answers (2)

David Heffernan
David Heffernan

Reputation: 612993

I'm assuming that you already have sorting capability in your code, and am not going to attempt to explain how to sort here. The RTL provides TArray.Sort<T> for this purpose.

Instead of sorting the values, sort indices. Add a level of indirection.

  1. Create an array of integer, Indices, containing the indices 0, 1, ..., N-1.
  2. Sort this array of integers.
  3. When comparing two values L and R from the array of indices, instead of comparing L and R, compare X[L] and X[R].

So, to expand on the final point, a standard compare function when sorting integers looks like this:

function Compare(L, R: Integer): Integer;
begin
  if L<R then
    Result := -1
  else if L>R then
    Result := 1
  else
    Result := 0;
end;

But instead, you apply indirection at this point:

function Compare(L, R: Integer): Integer;
begin
  if X[L]<X[R] then
    Result := -1
  else if X[L]>X[R] then
    Result := 1
  else
    Result := 0;
end;

At the end of this process you have indices that tell you the order of the points. The ith point is:

X[Indices[i]], Y[Indices[i]]

This technique is known as indirect sorting.

The problem that you present does suggest though that you may not have defined your data structures correctly. Instead of two distinct arrays, one containing the X coordinates, and one containing the Y coordinates, it would seem more appropriate to store a single array of points:

type
  TPoint = record
    X: Real;
    Y: Real;
  end;

var
  Points: array of TPoint;

Now you can sort Points by ordering on the X values, but exchanging entire points. When you represent the data this way, there is no possibility for the coordinates to get jumbled up. And X coordinate can never get separated from its matching Y coordinate.

Upvotes: 9

Bjarke Moholt
Bjarke Moholt

Reputation: 323

I think I've figured out the way to do it: 1) make a temporary array that is a copy of the input 2) find the minimum value of the temporary array 3) store the index of the minimum value 4) set the minimum value to NaN in the temporary array 5) repeat 2-5 until the temporary array no longer has numbers

Function indexedSort( inputArray : array of real ) : array of integer;
var
  i,j : integer;
  n : integer;
  minVal : real;
  tempArray : TArrayOfReal;
begin
  n := length(inputArray);
  setLength(result,n);
  tempArray := copy(inputArray,0,n);
  for i:= 0 to n-1 do begin
    for j := 0 to n-1 do begin
      if not(IsNan(tempArray[j])) then begin //find any non-NaN value for minimum
        minVal := tempArray[j];
        break;
      end;
    end;
    for j:=0 to n-1 do begin  //find actual min val
      if not(isNan(tempArray[j])) then begin
        if tempArray[j] <= minVal then begin
          minVal := tempArray[j];
          result[i] := j;
        end;
      end;
    end;
    tempArray[result[i]] := NaN;
  end;
end;

Upvotes: 1

Related Questions