Dynamisches Array of Integer sortieren: welches Sortierverfahren???

[romber]

Hallo!

Ich habe da ein Array of Integer, das in der Regel nicht mehr als 20-25 Zahlen drin hat. Die Zahlenwete liegen immer zwischen 1 und 128.

Nun möchte ich die Zahlen in diesem Array sortieren. Da bin ich auf eine Reihe von Sortiertutorials (hier) von Daniel gestossen. Welche der dort präsentierten Methoden ist in meinem Fall wirklich die schnellste? Klar, bei derart kleinen Datenmengen wird der Unterschied kaum bemerkbar sein. Trodzdem gibt es immer eine Methode, die schneller ist.

Danke!

[himitsu]

Kommt es hier wirklich auf jede kleine Microsekunde an?
Wie oft wird denn sortiert?

Nja, ich würde einfach ein Bubble-Sort implementieren und fertig.
Schön einfach und bestimmt ausreichend.

Bei den paar "klitzekleinen" Integer könnte schon alleine das Selection-Sort langsamer oder zumindestens gleich schnell sein,
so daß sich der Aufand einfach nicht lohnt.

[jfheins]

Bucketsort sollte die Aufgabe recht zügig bewältigen

Ansonsten: Diese Datenmenge ist ein Witz für jeden anständigen Algo. Alles außer Slowsort und Bogosort sollte den Job im Nu getan bekommen.

[Uwe Raabe]

Ich würde hier gar nichts implementieren sondern einfach folgendes aufrufen:

Delphi-Quellcode:

var
  MyArray: array of Integer;
...
  TArray.Sort<Integer>(MyArray);

Vorausgesetzt natürlich, man setzt keine veraltete Delphi-Version ein (Ich sehe gerade, daß dies der Fall ist)

Wenn's denn wirklich an der Performance drückt, kann man die Implementierung immer noch verbessern. Aber jede zusätzliche (und in diesem Fall völlig überflüssige) Implementierung ist eine zusätzliche Fehlerquelle.

[romber]

Vielen Dank für schnelle Raktionen!

Zitat von Uwe Raabe:

Ich würde hier gar nichts implementieren sondern einfach folgendes aufrufen:
  TArray.Sort<Integer>(MyArray);

Ob diese Methode auch die schnellste ist? Mir geht's wirklich um Performance. Ich erhalte über eine Schnittstelle sehr viele serialisierte Daten, die ich mittels Lookup-Funktionen in lesbare Form konvertieren muss. Manchmal sind es über 200 Datensätze pro Sekunde. Deswegen mache ich mir Sorgen um Performance.

Ich arbeite mittlerweise mit Delphi 2010, muss also klappen. Was muss ich für TArray in uses deklarieren?

[daywalker9]

uses Generics.Collections;

[Hawkeye219]

Hallo romber,

bei kleinen Zahlenmengen werden die herkömmlichen Sortierverfahren wahrscheinlich schnell genug sein. Der folgende Code beschreibt einen anderen Ansatz für nahezu beliebig große Zahlenmengen mit beschränktem Wertebereich:

Delphi-Quellcode:

procedure Sort (var A: array of Integer);
const
  MINVALUE = 1;
  MAXVALUE = 128;
  ERRVALUE = 255;
var
  i, j, k: Integer;
  Counter: array [MINVALUE..MAXVALUE] of Integer;
begin
  FillChar (Counter, SizeOf(Counter), 0);

  for i in A do
    if (i >= MINVALUE) and (i <= MAXVALUE) then
      Inc (Counter[i]);

  k := 0;
  for i := Low(Counter) to High(Counter) do
    for j := 1 to Counter[i] do
      begin
        A[k] := i;
        Inc (k);
      end;

  for j := k to High(A) do
    A[j] := ERRVALUE;
end;

Gruß Hawkeye

[rollstuhlfahrer]

also generell das allerschnellste Sortierverfahren, das es zur Zeit gibt und mir bekannt ist, ist QuickSort.
Delphi bringt auch Demos mit. Da ist eine Thread-Sortier-Demo dabei. Da könntest du mal schauen.
Da QuickSort rekursiv arbeitet, wird es etwas Performance schlucken. Wenn du den Stack nicht allzu stark belasten darfst, könnte MinSort (welches schneller ist als BubbleSort) auch zu gebrauchen sein.

Bernhard

EDIT: Noch was zur Performance: Array of Byte bei Zahlen unter 256 belegt 3 Byte weniger Speicherplatz pro Element

[Luckie]

Warum müssen die Daten in "Echtzeit" verarbeitet werden? Für so was eignet sich ein Threadpool, dann kann die Abarbeitung auch mal länger dauern, ohne dass du Probleme bekommst, wenn wieder Daten eintreffen.

[Uwe Raabe]

Zitat von rollstuhlfahrer:

also generell das allerschnellste Sortierverfahren, das es zur Zeit gibt und mir bekannt ist, ist QuickSort.

TArray.Sort benutzt QuickSort.

Zitat von rollstuhlfahrer:

Noch was zur Performance: Array of Byte bei Zahlen unter 256 belegt 3 Byte weniger Speicherplatz pro Element

Ist aber durch die 32-Bit Prozessor-Architektur langsamer im Zugriff als array of Integer.