배열을 정렬하는 가장 좋은 방법

StackOverflow https://stackoverflow.com/questions/41733

  •  09-06-2019
  •  | 
  •  

문제

레코드의 필드 중 하나를 기준으로 정렬하려는 레코드 배열이 있다고 가정해 보겠습니다.이를 달성하는 가장 좋은 방법은 무엇입니까?

TExample = record
  SortOrder : integer;
  SomethingElse : string;
end;

var SomeVar : array of TExample;
도움이 되었습니까?

해결책

배열 요소에 대한 포인터를 추가할 수 있습니다. TList, 그런 다음 전화하세요 TList.Sort 비교 함수를 사용하여 마지막으로 새 배열을 만들고 원하는 순서로 TList에서 값을 복사합니다.

그러나 다음 버전인 D2009를 사용하는 경우 배열을 정렬할 수 있는 새로운 컬렉션 라이브러리가 있습니다.선택사항이 필요합니다. IComparer<TExample> 사용자 정의 정렬 순서 구현.귀하의 특정 사례에 대한 조치는 다음과 같습니다.

TArray.Sort<TExample>(SomeVar , TDelegatedComparer<TExample>.Construct(
  function(const Left, Right: TExample): Integer
  begin
    Result := TComparer<Integer>.Default.Compare(Left.SortOrder, Right.SortOrder);
  end));

다른 팁

(1년이 지났지만 여전히 유용한 정보입니다.)

정수 값을 채우는 Skamradt의 제안은 문자열 비교를 사용하여 정렬한다고 가정합니다.이것은 느릴 것입니다.각 삽입에 대해 format()을 호출하지만 여전히 느립니다.대신 정수 비교를 원합니다.

레코드 유형으로 시작합니다. 

TExample = record
  SortOrder : integer;
  SomethingElse : string;
end;

레코드가 어떻게 저장되었는지 또는 정렬된 후 레코드에 액세스하려는 방법을 명시하지 않았습니다.따라서 이를 동적 배열에 넣었다고 가정해 보겠습니다. 

var MyDA  Array of TExample; 
...
  SetLength(MyDA,NewSize);           //allocate memory for the dynamic array
  for i:=0 to NewSize-1 do begin        //fill the array with records
    MyDA[i].SortOrder := SomeInteger;
    MyDA[i].SomethingElse := SomeString;
  end;

이제 정수 값 SortOrder를 기준으로 이 배열을 정렬하려고 합니다.원하는 것이 TStringList인 경우(ts.Find 메서드를 사용할 수 있음) 각 문자열을 목록에 추가하고 SortOrder를 포인터로 추가해야 합니다.그런 다음 포인터를 정렬합니다. 

var  tsExamples: TStringList;         //declare it somewhere (global or local)
...
  tsExamples := tStringList.create;   //allocate it somewhere (and free it later!)
...
  tsExamples.Clear;                   //now let's use it
  tsExamples.sorted := False;         //don't want to sort after every add
  tsExamples.Capacity := High(MyDA)+1 //don't want to increase size with every add
                                      //an empty dynamic array has High() = -1
  for i:=0 to High(MyDA) do begin
    tsExamples.AddObject(MyDA[i].SomethingElse,TObject(MyDA[i].SortOrder));
  end;

TStringList.Object 속성에 저장된 TObject 포인터에 정수 SortOrder를 캐스팅하는 방법에 주목하세요.(이는 Integer와 Pointer의 크기가 동일하다는 사실에 따라 달라집니다.) 어딘가에서 TObject 포인터를 비교하는 함수를 정의해야 합니다. 

function CompareObjects(ts:tStringList; Item1,Item2: integer): Integer;
var i,j: integer;
begin
  Result := integer(ts.Objects[i]) - integer(ts.Objects[j];
end;

이제 .Sort(문자열 값을 기준으로 정렬) 대신 .CustomSort를 호출하여 .Object에서 tsList를 정렬할 수 있습니다. 

tsExample.CustomSort(@CompareObjects);     //Sort the list

이제 TStringList가 정렬되었으므로 0에서 .Count-1까지 반복하고 정렬된 순서로 문자열을 읽을 수 있습니다.

그러나 TStringList를 원하지 않고 단지 정렬된 순서의 배열을 원한다고 가정해 보십시오.또는 레코드에 이 예의 문자열 하나보다 더 많은 데이터가 포함되어 있어 정렬 순서가 더 복잡합니다.모든 문자열을 추가하는 단계를 건너뛰고 배열 인덱스를 TList의 항목으로 추가하면 됩니다.TStringList 대신 TList를 사용하는 것을 제외하고 위의 모든 작업을 동일한 방식으로 수행합니다.

var Mlist: TList;                 //a list of Pointers
...
  for i:=0 to High(MyDA) do
    Mlist.add(Pointer(i));        //cast the array index as a Pointer
  Mlist.Sort(@CompareRecords);    //using the compare function below

function CompareRecords(Item1, Item2: Integer): Integer;
var i,j: integer;
begin
  i := integer(item1);            //recover the index into MyDA
  j := integer(item2);            // and use it to access any field
  Result := SomeFunctionOf(MyDA[i].SomeField) - SomeFunctionOf(MyDA[j].SomeField);
end;

이제 Mlist가 정렬되었으므로 이를 조회 테이블로 사용하여 정렬된 순서로 배열에 액세스합니다.

  for i:=0 to Mlist.Count-1 do begin
    Something := MyDA[integer(Mlist[i])].SomeField;
  end;

TList를 반복하면서 정렬된 순서로 배열 인덱스를 가져옵니다.TList는 포인터라고 생각하기 때문에 정수로 다시 캐스팅하면 됩니다.

나는 이런 방식을 좋아하지만 인덱스 대신 배열 요소의 주소를 추가하여 TList의 배열 요소에 대한 실제 포인터를 넣을 수도 있습니다.그런 다음 이를 사용하려면 TExample 레코드에 대한 포인터로 캐스팅합니다.Barry Kelly와 CoolMagic이 답변에서 이렇게 말했습니다.

문자열로 정렬해야 하는 경우 sorted를 사용하세요. TStringList 그리고 기록을 추가하십시오 TString.AddObject(string, Pointer(int_val)).

그러나 정수 필드와 문자열로 정렬이 필요한 경우 - 사용 TObjectList 모든 레코드 호출을 추가한 후 TObjectList.Sort 필요한 정렬 기능을 매개변수로 사용합니다.

이는 모두 정렬하는 레코드 수에 따라 다릅니다.수백 개 미만만 정렬하는 경우 다른 정렬 방법이 제대로 작동합니다. 더 많이 정렬하려면 오래되고 신뢰할 수 있는 Turbo Power를 잘 살펴보십시오. SysTools 프로젝트.소스에는 아주 좋은 정렬 알고리즘이 포함되어 있습니다.수백만 개의 레코드를 효율적인 방식으로 정렬하는 작업을 매우 훌륭하게 수행하는 제품입니다.

레코드 목록을 정렬하는 tStringList 메서드를 사용하려는 경우 목록에 삽입하기 전에 정수가 오른쪽에 채워졌는지 확인하세요.당신은 사용할 수 있습니다 format('%.10d',[rec.sortorder]) 예를 들어 10자리를 오른쪽으로 정렬하려면

Quicksort 알고리즘은 빠른 정렬이 필요할 때 자주 사용됩니다.예를 들어 Delphi는 List.Sort에 이를 사용하고 있습니다.Delphi List는 무엇이든 정렬하는 데 사용할 수 있지만 구조에 대한 포인터 배열처럼 보이는 무거운 컨테이너입니다.이 스레드에서 Guy Gordon과 같은 트릭을 사용하더라도 무겁습니다(인덱스나 포인터 대신 다른 것을 넣거나 32비트보다 작은 경우 직접 값을 넣기).목록 등을 구성해야 합니다.

결과적으로 구조체 배열을 쉽고 빠르게 정렬하는 대안은 다음을 사용하는 것입니다. qsort C 런타임 기능 msvcrt.dll에서.

다음은 좋을 수 있는 선언입니다(경고:Windows에서만 이식 가능한 코드).

type TComparatorFunction = function(lpItem1: Pointer; lpItem2: Pointer): Integer; cdecl;
procedure qsort(base: Pointer; num: Cardinal; size: Cardinal; lpComparatorFunction: TComparatorFunction) cdecl; external 'msvcrt.dll';

전체 예시 여기.

레코드가 큰 경우 레코드 배열을 직접 정렬하는 것이 느릴 수 있습니다.이 경우 레코드에 대한 포인터 배열을 정렬하는 것이 더 빠를 수 있습니다(어쨌든 목록 접근 방식과 비슷함).

배열을 사용하면 다음 중 하나를 사용합니다. quicksort 아니면 아마도 heapsort, 비교를 사용하도록 변경하면 됩니다. TExample.SortOrder, 스왑 부분은 여전히 ​​배열 및 스왑 포인터에만 작동합니다.배열이 매우 큰 경우 삽입 및 삭제가 많으면 연결 목록 구조가 필요할 수 있습니다.

C 기반 루틴, 여기에는 여러 가지 루틴이 있습니다.http://www.yendor.com/programming/sort/

다른 사이트이지만 파스칼 소스가 있음http://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html

다음이 제안하는 정렬 알고리즘 중 하나를 사용하세요. 위키피디아.Swap 함수는 배열 요소와 동일한 유형의 임시 변수를 사용하여 배열 요소를 교환해야 합니다.동일한 SortOrder 정수 값을 가진 항목을 처음 순서대로 유지하려면 안정적인 정렬을 사용하세요.

TStringList 효율적인 정렬 방법이 있습니다.
정렬을 원하면 TStringList 반대하다 Sorted 속성을 True로 설정합니다.

메모:속도를 높이려면 정렬되지 않은 개체를 추가하세요. TStringList 마지막에 속성을 True로 변경합니다.
메모:정수 필드를 기준으로 정렬하려면 문자열로 변환하세요.
메모:중복된 값이 있는 경우 이 방법은 유효하지 않습니다.

문안 인사.

Delphi XE2 이상이 있는 경우 다음을 시도해 볼 수 있습니다.

var 
  someVar: array of TExample;
  list: TList<TExample>;
  sortedVar: array of TExample;
begin
  list := TList<TExample>.Create(someVar);
  try
    list.Sort;
    sortedVar := list.ToArray;
  finally
    list.Free;
  end;
end;

정렬 필드가 문자열인 경우 올바르게 작동하는 매우 간단한 예제를 만들었습니다.

Type
  THuman = Class
  Public
    Name: String;
    Age: Byte;
    Constructor Create(Name: String; Age: Integer);
  End;

Constructor THuman.Create(Name: String; Age: Integer);
Begin
  Self.Name:= Name;
  Self.Age:= Age;
End;

Procedure Test();
Var
 Human: THuman;
 Humans: Array Of THuman;
 List: TStringList;
Begin

 SetLength(Humans, 3);
 Humans[0]:= THuman.Create('David', 41);
 Humans[1]:= THuman.Create('Brian', 50);
 Humans[2]:= THuman.Create('Alex', 20);

 List:= TStringList.Create;
 List.AddObject(Humans[0].Name, TObject(Humans[0]));
 List.AddObject(Humans[1].Name, TObject(Humans[1]));
 List.AddObject(Humans[2].Name, TObject(Humans[2]));
 List.Sort;

 Human:= THuman(List.Objects[0]);
 Showmessage('The first person on the list is the human ' + Human.name + '!');

 List.Free;
End;
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top