Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Zahlen sortieren ohne if?


DarkCell - So 26.03.06 13:37
Titel: Zahlen sortieren ohne if?
Ich habe sechs Int-Variablen: Z1, Z2, Z3, Z4, Z5, Z6 wahlweise auch ein array[1..6]
Jede dieser Variable hat eine zufällige Zahl.
Jetzt möchte ich in der ersten Variable(/Spalte des arrays) die höchste Zahl, in der zweiten die zweithöchste, und so weiter ...

Gibt es eine "schönere" bzw bequemere Möglichkeit, dass Problem zu lösen ohne ewige if-Entscheidungen?

Danke schonmal im voraus
DarkCell


Moderiert von user profile iconChristian S.: Topic aus Sonstiges (Delphi) verschoben am So 26.03.2006 um 15:20


Gausi - So 26.03.06 13:56

Ganz ohne Ifs wirds nicht gehen ;-)

Aber such mal nach Suche in der Entwickler-Ecke BUBBLESORT. Das dürfte für deine Zwecke am geeignetsten sein.


zemy - Di 28.03.06 21:48

Bubblesort, Quicksort, Shellsort, Bogosort.... Wiki unter Sortieralgorythmen. Da gibtsschon was. Ist schon was zu finden. Aber ohne If? Natülich!


Delphi-Quelltext
1:
2:
if (a[i]>a[j])
  tausche(a[i],a[j]);


wird zu

Delphi-Quelltext
1:
2:
while (a[i]>a[j])
  tausche(a[i],a[j]);


Obn das elegant ist, wage ich zu bezweifeln :P

MfG


Noodles - Di 28.03.06 22:22

Geht es Dir darum einen Algorithmus selbst zu entwickeln, oder eine vorhandenen Lösung zu finden?
Wenn es das Letztere ist, dann sollte Dir folgendes helfen.


C#-Quelltext
1:
2:
3:
int[] values = { 52832217 };
Array.Sort<int>(values);
Array.Reverse(values);


MightyPit - Mi 12.04.06 09:12

Hmm das Funktioniert in Delphi so aber nicht. Ein Array ist in Delphi kein Objekt sondern ein eigenes Sprachmittel. Wenn man eine Liste verwendet kann man sortieren lassen. aber die Vergleichsfunktion muss man selber machen, und darin sind auch wieder mindestens 2 if enthalten
Suche in: Delphi-Forum TLIST SORTIERPROBLEM


alzaimar - Mi 12.04.06 09:47

Ohne einen Vergleich wird und kann es nicht gehen. Aber ohne 'ständige' Vergleiche schon. In Bubble/Insertionsort etc. ist sogar nur jeweils ein 'IF' zu finden, insofern kommen diese Algorithmen schon ohne ständige If's aus :wink:


Robert_G - Mi 12.04.06 10:30

Ohne bedingte Sprünge wird man wohl nicht sortieren können. :mrgreen:
Man kann es höchstens so deichseln, dass man sie nicht im selbst geschriebenen Code enthält sondern an TList delegiert. :lol:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
uses
  Classes;

  function CompareInts(left, right : PInteger) : Integer;
  begin
    Result := left^ - right^;
  end;

  procedure Print(list : TList);
  var
    i : Integer;
  begin
    for i := 0 to list.Count - 1 do
    begin
      Writeln(PInteger(list[i])^);
    end;
  end;

var
  list : TList;

  procedure Add(const items : array of Integer);
  var
    i : Integer;
  begin
    for i := Low(items) to High(items) do
    begin
      list.Add(@items[i]);
    end;
  end;
begin
  list := TList.Create();
  try
    Add([52832217]);

    list.Sort(@CompareInts);

    Print(list);
  finally
    list.Free();
  end;
end.


Spaceguide - Mi 12.04.06 10:34

Geht schon ohne IF's:


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
procedure Sortiere(var a,b : integer);
 var temp : integer;
begin
 temp := a;

 a := (-abs(a-b)+(a+b)) div 2;
 b := (abs(temp-b)+(temp+b)) div 2;
end;


*hoffentlich merkt keiner den Beschiss* ;-)


zemy - Mi 12.04.06 17:18

wie währe es da mit...

Delphi-Quelltext
1:
2:
3:
4:
procedure Sortiere(int x):int
begin
result:=x;
end;


Spaceguide - Mi 12.04.06 17:24

1) Das sortiert nix
2) Procedures geben keine Werte zurück
3) Den Datentyp int gibt es in Delphi nicht
4) Bei der Deklaration einer Variablen wird der Datentyp nachgestellt und durch einen Doppelpkt. vom Variablennamen getrennt
5) Nach der Angabe des Rückgabewerts einer Funktion muss ein Strichpkt. folgen


Aristoteles - Do 13.04.06 14:24
Titel: Re: Zahlen sortieren ohne if?
user profile iconDarkCell hat folgendes geschrieben:

Gibt es eine "schönere" bzw bequemere Möglichkeit, dass Problem zu lösen ohne ewige if-Entscheidungen?


Nein. Ohne zwei Zahlen miteinander zu vergleichen kann man nicht feststellen, welche die größere ist.

Auch fremde Routinen wie z.B. Bubblesort müssen auf den If-Befehl zurückgreifen.


Spaceguide - Do 13.04.06 14:53

Man KANN entscheiden, welches die größere/kleinere Zahl von zwei Zahlen ist, ohne eine Fallunterscheidung zu verwenden, und zwar mit der obigen Routine von mir. Abs ist zwar oft als Fallunterscheidung implementiert, aber das lässt sich ja umgehen:

Größere Zahl von a und b: (Sqrt(Sqr(a-b))+(a+b))/2


jasocul - Do 13.04.06 14:59

Damit kannst du den Wert der größeren Zahl bestimmen (Formel habe ich nicht geprüft), aber du weißt immer noch nicht welche die größere ist.


Spaceguide - Do 13.04.06 15:11

Eine Zahl wird ja auch nur über ihren Wert definiert.


Horschdware - Do 13.04.06 15:22

ja gut. dann weisst du wie groß die beiden sind. aber du weisst nicht welche größer ist.
das ist wie bei kuchen: vom ansehen und der beschreibung her weiss du dass zwei kuchen lecker sind. du könntest dir sogar beschreiben lassen WIE lecker sie sind. aber ohne probiert zu haben kannst du trotzdem keinen vergleich ziehen.

btw: ...die größere zahl herausfinden ist ja ein vergleich.
und wie mache ich einen vergleich ohne einen vergleich zu machen? eigentlich nicht...


Spaceguide - Do 13.04.06 15:38

Von was redet ihr hier eigentlich? Kuchen?!?!

Hier der Beweis:


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
procedure Sortiere(var aNumbers : array of double);
 var temp : double;
     i,j : integer;
begin
 for i:=Low(aNumbers) to High(aNumbers)-1 do
  for j:=i+1 to High(aNumbers) do
  begin
   temp := aNumbers[i];
   aNumbers[i] := (-Sqrt(Sqr(aNumbers[i]-aNumbers[j]))+
                           (aNumbers[i]+aNumbers[j]))*0.5;
   aNumbers[j] := (Sqrt(Sqr(temp-aNumbers[j]))+
                           (temp+aNumbers[j]))*0.5;
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
 var zahlen : array of double;
     i : integer;
begin
 setlength(zahlen,100);
 for i:=Low(zahlen) to High(zahlen) do zahlen[i]:=Random*100;
 Sortiere(zahlen);
 for i:=Low(zahlen) to High(zahlen) do
  memo1.lines.add(floattostr(zahlen[i]));
end;


DaRkFiRe - Do 13.04.06 16:13

Ich vermute mal, dass er das Array / die Zahlen und dessen Sortierung fest im Source verankert hatte, anstatt über Schleifen zu iterieren oder über Funktionen zu rekursieren.


jasocul - Do 13.04.06 16:45

@Spaceguide:
Das Verfahren kann ich nachvollziehen. Über den Sinn lässt sich streiten. :wink:


delfiphan - Fr 14.04.06 11:17

=> Bucketsort [http://de.wikipedia.org/wiki/Bucketsort]


Robert_G - Fr 14.04.06 12:46

user profile icondelfiphan hat folgendes geschrieben:
=> [url=http://de.wikipedia.org/wiki/Bucketsort]Bucketsort[/url]
Benutzt ebenfalls bedingte Sprpünge. ;)


Horst_H - Fr 14.04.06 13:36

Hallo,

dem Wahnsinn eine Chance, eine kleine Optimierung ;-).


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
procedure Sortiere(var aNumbers : array of double);
 var AbsDiff,Summ : double;
     pAi,pAj : ^double;
     pInt32 :^Cardinal;
     i,j : integer;
begin
 pInt32 := @AbsDiff;
 inc(pInt32);//wegen double und little endian
 pAi := @aNumbers[High(aNumbers)-1];
 // High(aNumbers) wird nur einmal abgefragt statt jedesmal
 for i:= High(aNumbers)-1 downto 0 do
   begin
   pAj := @aNumbers[High(aNumbers)];
   for j:=High(aNumbers) downto 1 do
     begin
     AbsDiff := pAi^-pAj^;
     // Vorzeichen auf + setzen
     pInt32^:=pInt32^ AND $7FFFFFFF;
     Summ :=pAi^+pAj^;
     pAi^ := (Summ-AbsDiff)*0.5;
     pAj^ := (Summ+AbsDiff)*0.5;
     dec(pAj);
     end;
   dec(pAi);
   end;
end;


Gruss Horst


zemy - Fr 14.04.06 14:07

user profile iconSpaceguide hat folgendes geschrieben:
1) Das sortiert ni
2) Procedures geben keine Werte zurück
3) Den Datentyp int gibt es in Delphi nicht
4) Bei der Deklaration einer Variablen wird der Datentyp nachgestellt und durch einen Doppelpkt. vom Variablennamen getrennt
5) Nach der Angabe des Rückgabewerts einer Funktion muss ein Strichpkt. folgen

Schon ein Problem, wenn man Stundenlang C/C++ schreibt und dann sich Delphi-Code ausm Ärmel Schütteln soll... Aber es sortiert trotzdem;) Ein einzelner Wert ist sortiert ^^


delfiphan - Fr 14.04.06 15:11

Bucketsort macht keine Vergleiche. Bucketsort funktioniert vereinfacht ungefähr so:

Sortiere die Buchstaben im Wort "elephant". Dabei wird einfach gezählt welcher Buchstabe wie häufig vorkommt. Das heisst:
1x"a", 2x"e", 1x"h", 1x"l", 1x"n", 1x"p", 1x"t"

Das kannst du ungefähr so machen:

Delphi-Quelltext
1:
2:
for I := 1 to length(S) do
 inc(Haeuffigkeit[S[I]]);
Danach gibst du einfach das Resultat aus...

Das ganze Spielchen kann man dann auch in mehrere Schritte unterteilen. Verglichen hast du die Zahlen bzw. Buchstaben untereinander jedoch nie.

Bei Wikipedia gibt's ein Codeschnipsel in Pascal. Im Code kommt nirgends ein "if", ein "=", "<" oder ">" vor. Auch keine while oder repeat Schleifen. Nur fest vorgegebene for-Schleifen.


nullplan001 - Fr 14.04.06 15:39

Es war ja nur gefragt, ob man denn "if" rauslassen könne. Klar, das geht:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
procedure sortarray(var a:array of word); assembler;
label loop1, endloop;
asm
  lea cx,a
  loop1:
    mov ax,[cx]
    add cx,2
    mov bx,[cx]
    cmp ax,bx
    jz endloop {beide gleich -> nix zu tun}
    jns endloop { a größer b -> nix zu tun}
    sub cx,2
    mov bx,[cx]
    add cx,2
    mov ax,[cx] 
    endloop:
    push offset a
    call sizeof
    cmp cx,ax
    jnz loop1
end;


Spaceguide - Fr 14.04.06 15:48

Das "IF" ist nicht wörtlich gemeint. Das Problem ist eine Sortierung ohne Verzweigungen.


Horst_H - Fr 14.04.06 15:59

Hallo,

bei Bucketsort muss aber noch etwas hinzukommen, das Du naemlich einen sehr eingeschraenkten Wertebereich.
Siehe [url=http://www.linux-related.de/index.html?/coding/sort/sort_radix.htm]Hier[/url] bei linstraightradix.

Dies gilt fuer Fliesskommazahln nun meist garnicht.
Aber auch da kann man erst nach Mantissenbytes und dann nach Exponent sortieren.
Dazu muss aber die Anordnung im Speicher genau kennen und es erschliesst sich nicht so leicht.

Hast Du soetwas schon umgesetzt.

Gruss Horst


F34r0fTh3D4rk - Fr 14.04.06 16:31

user profile iconSpaceguide hat folgendes geschrieben:
Von was redet ihr hier eigentlich? Kuchen?!?!

Hier der Beweis:


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
procedure Sortiere(var aNumbers : array of double);
 var temp : double;
     i,j : integer;
begin
 for i:=Low(aNumbers) to High(aNumbers)-1 do
  for j:=i+1 to High(aNumbers) do
  begin
   temp := aNumbers[i];
   aNumbers[i] := (-Sqrt(Sqr(aNumbers[i]-aNumbers[j]))+
                           (aNumbers[i]+aNumbers[j]))*0.5;
   aNumbers[j] := (Sqrt(Sqr(temp-aNumbers[j]))+
                           (temp+aNumbers[j]))*0.5;
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
 var zahlen : array of double;
     i : integer;
begin
 setlength(zahlen,100);
 for i:=Low(zahlen) to High(zahlen) do zahlen[i]:=Random*100;
 Sortiere(zahlen);
 for i:=Low(zahlen) to High(zahlen) do
  memo1.lines.add(floattostr(zahlen[i]));
end;


wo er recht hat... ;) ihm geht es auch wohl nur darum nicht jede zahl mit jeder vergleichen zu müssen, ihm wurden genug wege genannt, es wurden genug wege genannt, dann sollte auch irgendwann mal gut sein ;)


delfiphan - Fr 14.04.06 21:34

user profile iconSpaceguide hat folgendes geschrieben:
Das Problem ist eine Sortierung ohne Verzweigungen.

Das Problem ist nicht eine Sortierung ohne Verzweigungen. Er hat ein Array und möchte die möglichst ohne eine komplizierte Sortierroutine sortieren. Dabei geht es nicht darum, ob man ein min(a,b) mathematisch zu einem Audruck mit abs() bzw sqrt(sqr()) umformulieren kann.

Es ist nicht meine Aufgabe, die Threads sauber zu halten. Aber: Er hat lediglich gefragt, ob man 6 Integer-Zahlen möglichst ohne grosse IF-Entscheidungen sortieren kann. Alles andere ist dazugedichtet. DarkCell hat seit dem ersten Post nie mehr was von sich gegeben. Die vielen Hacks hier beantworten imho weder seine Frage noch sind die meisten Codeschnipsel ihm in irgend einer Weise dienlich.

Meine Antwort auf seine Frage: Ja, es ist unter Umständen möglich, aber nicht so, wie du es dir wohl vorstellst. Wenn du ein Array sortieren willst hast du zwingend eine For-Schleife und bei allen klassischen Sortieralgorithmen musst du Zahlen vergleichen (eine Ausnahme ist Bucketsort). Bucketsort hat zwar eine lineare Sortierzeit, ist aber bei einer so kleinen Datenmenge (6 Integers) überhaupt nicht zu empfehlen.


Jan11 - Mo 17.04.06 17:20

Man kann sie auch einfach in eine Tstringlist schreiben, und da gibt es den befehl Mystringlist.sort; ... dann kannst du sie einfach wieder einlesen


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
procedure ordnen
var(i : integer, mystringlist : Tstringlist, werte : array[1..6of integer);

begin
mystringlist:=Tstringlist.create;

for i := 1 to 6 do begin
   Mystringlist.add(inttostr(werte[i]));
end;

mystringlist.sort;

for i := 1 to 6 do begin
   werte[i]:=strtoint(mystringlist.strings[i-1]);
end;


Mystringlist.free;

end;


und kann mir mal jemand sagen, wie ich das in sonen coolen delphi-quelltext schreiben kann?


F34r0fTh3D4rk - Mo 17.04.06 17:31

Benutzen auch du die Delphi Tags du sollst junger Padawan.

[delphi][/delphi]


Spaceguide - Mi 19.04.06 08:19

Jan11, da hast du aber überhaupt nicht nachgedacht. Zahlen als Werte zu sortieren ist gänzlich anders als Zahlen als Strings:


1
2
3
100
200
300

wird bei dir zu

1
100
2
200
3
300

sortiert.


TSittly - Di 25.04.06 16:38

Ich versteh euch nicht...als Assemblercode wird immer ein Compare verwendet... aber wen es dennoch interessiert: Hier ein Beispiel mit und eines ohne if.
In Delphi gibt es anscheinend keinen Bedingungsoperator wie in C:
#define Min(x,y) (x<y) ? x:y

Deshalb habe ich es so gemacht, hier mit if (einfaches BubbleSort)


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
procedure TForm1.Sort(var a:array of integer);
var t:integer;
i,j:integer;
begin
  t:=0;
  //Sortiere array
  for i:=0 to 8 do begin
    for j:=0 to 7 do begin
      if (a[j]>a[j+1]) then begin
        t:=a[j];
        a[j]:=a[j+1];
        a[j+1]:=t;
      end;
    end;
  end;
end;


Und hier das gleiche ohne if


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
procedure TForm1.Sort2(var a:array of integer);
var t:integer;
i,j:integer;
begin
  t:=0;
  //Sortiere array
  for i:=0 to 8 do begin
    for j:=0 to 7 do begin
      case (a[j]>a[j+1]) of
      True: begin
              t:=a[j];
              a[j]:=a[j+1];
              a[j+1]:=t;
            end;
      end;
    end;
  end;
end;


Wer kommt auf die Idee, so rechenintensive Sqrt dem if vorzuziehen?
Die Wahl des Algorithmus hängt mit von der Datenmenge ab, Bubblesort kann man gut für relativ kurze Listen verwenden, Quicksort ist zwar im schlechtesten Fall genauso lahm, aber im besten Fall dafür schneller ;-)


alzaimar - Di 25.04.06 17:32

Dreht es, wie ihr wollt: Spaceguide hat gewonnen (zu recht)!


Spaceguide - Fr 28.04.06 15:59

Hehe, thx. Die ganzen anderen "Lösungen" sind wie einfach das Fremdwort beim Spiel Tabu zu sagen.