CODEWITHSUNDEEP
delphidelphi-xe6
user3764855
user3764855

Reputation: 297

How to check if Array is sorted?

How can I check if TArray is already sorted? I am using the default TArray.Sort to sort my array.

Upvotes: 2

Views: 521

Answers (2)

David Heffernan
David Heffernan

Reputation: 612993

I do it like as below. In fact, my class has a load more goodies, I've just included the code to test whether arrays are ordered. I use TArray and hide the version in Generics.Collections, but derive from it to inherit its capabilities. This leads to code that reads better, although the use of hiding may make you feel queasy to begin with. 

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

type
  TSortType = (stIncreasing, stDecreasing);

  TArray = class(System.Generics.Collections.TArray)
  private
    class function Comparison<T>(SortType: TSortType): TComparison<T>; static;
    class function Comparer<T>(const Comparison: TComparison<T>): IComparer<T>; static;
  public
    class function Sorted<T>(var Values: array of T; SortType: TSortType; Index, Count: Integer): Boolean; overload; static;
    class function Sorted<T>(var Values: array of T; SortType: TSortType): Boolean; overload; static;
    class function Sorted<T>(var Values: array of T; const Comparison: TComparison<T>; Index, Count: Integer): Boolean; overload; static;
    class function Sorted<T>(var Values: array of T; const Comparison: TComparison<T>): Boolean; overload; static;
    class function Sorted<T>(GetValue: TFunc<Integer,T>; const Comparison: TComparison<T>; Index, Count: Integer): Boolean; overload; static;
  end;

class function TArray.Comparison<T>(SortType: TSortType): TComparison<T>;
var
  DefaultComparer: IComparer<T>;
begin
  DefaultComparer := TComparer<T>.Default;
  Result :=
    function(const Left, Right: T): Integer
    begin
      case SortType of
      stIncreasing:
        Result := DefaultComparer.Compare(Left, Right);
      stDecreasing:
        Result := -DefaultComparer.Compare(Left, Right);
      end;
    end;
end;

class function TArray.Comparer<T>(const Comparison: TComparison<T>): IComparer<T>;
begin
  Result := TComparer<T>.Construct(Comparison);
end;

class function TArray.Sorted<T>(var Values: array of T; SortType: TSortType; Index, Count: Integer): Boolean;
begin
  Result := Sorted<T>(Values, Comparison<T>(SortType), Index, Count);
end;

class function TArray.Sorted<T>(var Values: array of T; SortType: TSortType): Boolean;
begin
  Result := Sorted<T>(Values, Comparison<T>(SortType));
end;

class function TArray.Sorted<T>(var Values: array of T; const Comparison: TComparison<T>; Index, Count: Integer): Boolean;
var
  i: Integer;
begin
  for i := Index+1 to Index+Count-1 do begin
    if Comparison(Values[i-1], Values[i])>0 then begin
      Result := False;
      exit;
    end;
  end;
  Result := True;
end;

class function TArray.Sorted<T>(var Values: array of T; const Comparison: TComparison<T>): Boolean;
begin
  Result := Sorted<T>(Values, Comparison, 0, Length(Values));
end;

class function TArray.Sorted<T>(GetValue: TFunc<Integer, T>; const Comparison: TComparison<T>; Index, Count: Integer): Boolean;
var
  i: Integer;
begin
  for i := Index+1 to Index+Count-1 do begin
    if Comparison(GetValue(i-1), GetValue(i))>0 then begin
      Result := False;
      exit;
    end;
  end;
  Result := True;
end;

Upvotes: 2

MBo
MBo

Reputation: 80197

Check neighbour pairs with the same comparator as Sort uses

Result := True;
for i := Low(Arr) + 1 to High(Arr) do
  if Compare(Arr[i], Arr[i - 1]) < 0 then
    Exit(False);

It takes O(n) time (against O(nlogn) for sorting)

Upvotes: 7

Related Questions