Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren

[Furtbichler]

Leute, 5 SWAP-Operationen reichen aus. SWAP = IF a[j] > a[i] then exchange(a[i],a[j]);

[Aphton]

Warum 5, wenns auch mit 4 geht??
(Oder verstehe ich da etwas falsch?)

[hathor]

Sorting Algorithms in Delphi:
http://www.explainth.at/en/delphi/dsort.shtml

Hier gibt es ein schönes SORTDEMO:
http://www.explainth.at/downloads/dsort.zip

[Delphi-Laie]

Am schnellsten ist n.m.W. manch nichtvergleichendes Sortierverfahren, die sog. speziellen Sortieralgorithmen (sortieralgorithmen.de). Diese zählen einfach, wie oft jeder (vorher potentiell schon bekannte) Wert vorhanden ist, sie kommen mithin ohne Vergleiche und ohne Tauschungen aus. Da die Werte Bytes sind, sind nur 256 verschiedene Werte möglich. Geeignet wären z.B. Bucket- und Countingsort.

Ein Wermutstropfen ist jedoch dabei: Das Zielarray hätte 256 Werte (für die jeweiligen Anzahlen). Maximal 4 Werte wären jedoch verschieden von Null. Das wäre dann wohl doch etwas mit Kanonen auf Spatzen geschossen.

[Dano]

Danke für die vielen antworten, ich versuch mal paar versionen und messe die laufzeiten


mfg Dano

[himitsu]

Nur Versionen mit Schleifen werden im Prinzip nichts verbessern können, da bei den 4 Werten werden Schleifen mehr "bremsen", als man durch irgendeinen Algorithmus optimieren könnte.

Sind ja maximal 9, aber mit dem schlechteren Sortierungsalgo auch nur 6 Vergleiche, was man sowieso nur auf 4-5 minimieren könnte.
(1-2 gepsarte Vergleiche + eventuelles Tauschen sind kleiner als 1-2 Schleifen benötigen)

[Dano]

Delphi-Quellcode:

procedure Selectionsort3(var B: ByteArray);
var
  T: Byte;
begin
  With B do begin
    if A[0] > A[1] then begin T:= A[0]; A[0]:= A[1]; A[1]:= T; end;
    if A[0] > A[2] then begin T:= A[0]; A[0]:= A[2]; A[2]:= T; end;
    if A[0] > A[3] then begin T:= A[0]; A[0]:= A[3]; A[3]:= T; end;
    if A[1] > A[2] then begin T:= A[1]; A[1]:= A[2]; A[2]:= T; end;
    if A[1] > A[3] then begin T:= A[1]; A[1]:= A[3]; A[3]:= T; end;
    if A[2] > A[3] then begin T:= A[2]; A[2]:= A[3]; A[3]:= T; end;
  end;
end;

war bis jetzt der schnellste durchlauf^^

Code:

Memo1
D4SortByteArray
4347,1272 ms
Array: 1,2,3,4 - 16909060

D4SortByteArray2
7017,4326 ms
Array: 4,3,2,1 - 67305985

D4SortByteArray3
3949,3329 ms
Array: 4,3,2,1 - 67305985

NetworkSort
9294,5604 ms
Array: 4,3,2,1 - 67305985

Selectionsort
11118,2252 ms
Array: 4,3,2,1 - 67305985

Selectionsort2
3368,4371 ms
Array: 4,3,2,1 - 67305985

Selectionsort3
3150,7498 ms
Array: 4,3,2,1 - 67305985

Selectionsort4
3430,0005 ms
Array: 4,3,2,1 - 67305985

mfg Dano