La mejor manera de ordenar una matriz

Question

Supongamos que tengo una matriz de registros que quiero ordenar en función de uno de los campos en el registro. ¿Cuál es la mejor manera de lograr esto?

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

var SomeVar : array of TExample; 

Answer 1

Puede agregar punteros a los elementos de la matriz a TList, luego llamar al TList.Sort con una función de comparación, y finalmente crear una nueva matriz y copiar los valores fuera del TList en el orden deseado.

Sin embargo, si está utilizando la próxima versión, D2009, hay una nueva biblioteca de colecciones que puede ordenar matrices. Se necesita una implementación opcional de IComparer<TExample> para órdenes de clasificación personalizadas. Aquí está en acción para su caso específico:

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

Answer 2

Utilice uno de los alorithms ordenar por proponen Wikipedia. La función Swap debe intercambiar elementos de la matriz utilizando una variable temporal del mismo tipo que los elementos de la matriz. Utilice una clasificación estable si desea que las entradas con el mismo valor entero SortOrder permanezcan en el orden en que estaban en primer lugar.

Answer 3

Con una matriz, que haría uso de cualquiera quicksort o posiblemente heapsort, y sólo cambiar la comparación de usar TExample.SortOrder, la parte de intercambio todavía va a actuar en solo la matriz y los punteros de intercambio. Si la matriz es muy grande, es posible que desee una estructura de lista vinculada si hay una gran cantidad de inserción y eliminación.

basado en rutinas C, hay varios aquí http://www.yendor.com/programming/sort/

otro sitio, pero tiene en lenguaje Pascal http://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html

Answer 4

Si su necesidad ordenados por la cadena a continuación, el uso ordenadas TStringList y añadir registro por TString.AddObject(string, Pointer(int_val)).

Pero si es necesario ordenar por campo entero y cadena - use TObjectList y después de agregar todos los registros, llame al TObjectList.Sort con las funciones ordenadas necesarias como parámetro.

Answer 5

TStringList tienen método de clasificación eficiente.
Si desea ordenar utilice un objeto TStringList con la propiedad Sorted en True.

NOTA: Para obtener más velocidad, agregue objetos en un orden TStringList y al final cambie la propiedad a True.
NOTA: para clasificar por campo entero, conviértalo en cadena.
NOTA: Si hay valores duplicados, este método no es Válido.

Atentamente.

Answer 6

Todo esto depende del número de registros que está ordenando. Si solo está clasificando menos de unos cientos, los otros métodos de ordenación funcionan bien, si va a ordenar más, entonces eche un vistazo al viejo y confiable proyecto Turbo Power SysTools. Hay un algoritmo de ordenamiento muy bueno incluido en la fuente. Uno que hace un muy buen trabajo clasificando millones de registros de manera eficiente.

Si va a utilizar el método tStringList para ordenar una lista de registros, asegúrese de que su entero esté acolchado a la derecha antes de insertarlo en la lista. Puede usar el formato ('%. 10d', [rec.ordenar por ordenar]) para alinear a la derecha a 10 dígitos, por ejemplo.

Answer 7

(sé que esto es un año más tarde, pero todavía cosas útiles.)

sugerencia de Skamradt a valores enteros almohadilla asume que se va a ordenar mediante una cadena de comparar. Esto sería lento. Formato de llamada() para cada inserción, aún más lento. En cambio, quieres hacer una comparación de enteros.

Se empieza con un tipo de registro:

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

Usted no indicó cómo se almacenan los registros, o cómo quería acceder a ellos una vez ordenados. Así que vamos a suponer que los pone en una matriz dinámica:

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; 

Ahora que desea ordenar esta matriz por el valor entero SortOrder. Si lo que desea es un TStringList (para que pueda usar el método ts.Find), debe agregar cada cadena a la lista y agregar SortOrder como un puntero. A continuación, ordenar en el puntero:

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; 

Nota el truco de echar la Entero SortOrder en un puntero TObject, que se almacena en la propiedad TStringList.Object. (Esto depende del hecho de que enteros y Pointer son del mismo tamaño.) En algún lugar hay que definir una función para comparar los punteros: TObject

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

Ahora, podemos clasificar la tsList en .Object llamando .CustomSort vez de .Sort (que clasificar en el valor de cadena.)

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

el TStringList se ordenan ahora, por lo que puede iterar sobre ella de 0 a .Count-1 y leer las cadenas en el orden establecido.

Pero supongamos que no desea una TStringList, solo una matriz ordenada. O los registros contienen más datos que solo una cadena en este ejemplo, y su orden de clasificación es más complejo. Puede omitir el paso de agregar cada cadena y simplemente agregar el índice de matriz como Elementos en un TList. Hacer todo por encima de la misma manera, excepto utilizar un TList en lugar de TStringList:

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; 

Ahora que ListaM está ordenada, lo utilizan como una tabla de búsqueda para acceder a la matriz en forma ordenada:

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

Como itera sobre el TList, recuperamos los índices de matriz en orden ordenado. Solo tenemos que volver a convertirlos en números enteros, ya que TList cree que son punteros.

Me gusta hacerlo de esta manera, pero también podría poner punteros reales a los elementos de la matriz en TList al agregar la Dirección del elemento de la matriz en lugar de su índice. Luego, para usarlos, los lanzará como punteros a los registros de TExample. Esto es lo que Barry Kelly y CoolMagic dijeron que hicieran en sus respuestas.

Answer 8

El algoritmo de quicksort se usa a menudo cuando se requiere una clasificación rápida. Delphi está (O lo estaba) usándolo para List.Sort por ejemplo. La lista Delphi se puede utilizar para ordenar cualquier cosa, pero es un contenedor de gran peso, que se supone debe verse como una serie de punteros en las estructuras. Es un peso pesado incluso si usamos trucos como Guy Gordon en este hilo (poner índice o cualquier cosa en lugar de punteros, o poner valores directamente si son menores que 32 bits): tenemos que construir una lista y así sucesivamente ...

En consecuencia, una alternativa a ordenar una matriz de struct podría ser fácilmente y rápidamente a usar qsort C runtime function de msvcrt.dll.

Aquí hay una declaración que podría ser buena (Advertencia: código portátil en Windows solamente).

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

Ejemplo completo here.

Observe que la ordenación directa de la matriz de registros puede ser lenta si los registros son grandes. En ese caso, ordenar una matriz de puntero a los registros puede ser más rápido (de alguna manera, como el enfoque de lista).

Answer 9

Creé un ejemplo muy simple que funciona correctamente si el campo de clasificación es una cadena.

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; 

Answer 10

Si tiene Delphi XE2 o posterior, puede intentar:

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;