delphi - por - La mejor forma de ordenar una matriz

ordenar matriz por columna c++

Question

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

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

var SomeVar : array of TExample;

Answer 1

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

La sugerencia de Skamradt de rellenar valores enteros supone que va a ordenar utilizando una comparación de cadenas. 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.

Comienzas con un tipo de registro:

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

No indicó cómo se almacenaron los registros ni cómo quería acceder a ellos una vez que se ordenaron. Asumamos que los pones 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 quiere 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. Luego ordena 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;

Tenga en cuenta el truco de convertir el SortOrder entero en un puntero TObject, que se almacena en la propiedad TStringList.Object. (Esto depende del hecho de que Integer y Pointer tengan el mismo tamaño.) En algún lugar debemos 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 ordenar el tsList en .Object llamando a .CustomSort en lugar de .Sort (que ordenaría el valor de la cadena).

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

El TStringList ahora está ordenado, por lo que puede recorrerlo desde 0 hasta .Count-1 y leer las cadenas en orden ordenado.

Pero supongamos que no quiere 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. Haga todo por encima de la misma manera, excepto que use 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 Mlist está ordenado, úselo como una tabla de búsqueda para acceder a la matriz en orden ordenado:

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

A medida que repito 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 2

Con una matriz, usaría quicksort o posiblemente heapsort , y simplemente cambiaría la comparación para usar TExample.SortOrder , la parte de intercambio solo va a actuar en la matriz y cambiar punteros. 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.

Rutinas basadas en C, hay varias aquí http://www.yendor.com/programming/sort/

Otro sitio, pero tiene fuente pascal http://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html

Answer 3

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 4

El algoritmo de orden rápida se usa a menudo cuando se requiere una clasificación rápida. Delphi está (O lo estaba) usándolo para List.Sort por ejemplo. Delphi List se puede utilizar para ordenar cualquier cosa, pero es un contenedor pesado, que se supone que 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 para ordenar fácil y rápidamente una matriz de struct podría ser usar la función qsort C runtime 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 .

Tenga en cuenta que ordenar directamente la matriz de registros puede ser lento 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 5

Puede agregar punteros a los elementos de la matriz a un TList , luego llamar a TList.Sort con una función de comparación, y finalmente crear una nueva matriz y copiar los valores de 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 IComparer<TExample> 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 6

Si su necesidad se ordena por cadenas, utilice TStringList ordenado y agregue registro por TString.AddObject(string, Pointer(int_val)) .

Pero si necesita ordenar por campo entero y cadena - use TObjectList y luego de agregar todos los registros, TObjectList.Sort con las funciones ordenadas necesarias como parámetro.

Answer 7

Si tiene Delphi XE2 o una versión más nueva, 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;

Answer 8

Todo esto depende de la cantidad 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, 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.sortorder]) para alinear a la derecha a 10 dígitos, por ejemplo.

Answer 9

Usa uno de los aloritmos de ordenación propuestos por 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 10

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

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

Saludos.